[LeetCode 279.] Perfect Squres

LeetCode 279. Perfect Squres

DP 是笨办法中的高效办法,又是一道可以被好办法打败的 DP 题。

题目描述

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

解题思路

这道题是说,给出一个正整数 n,问可以最少用几个完全平方数的加和来表示。

我的第一个思路是 n = a + b (a <b) 然后用 DP 来消除重复计算,结果超时了,因为时间复杂度太高,到了 O(N^2) 级别。

另一个思路好一点,拆成 n = a + k*k 的形式,同样的 DP 算法,时间复杂度只有 O(NlogN)。

其实本题最佳算法可以达到 O(logN),用到了 Lagrange 四平方定理: 任何一个正整数都可以表示成不超过四个整数的平方之和。这里贴出来源和代码,仅作了解。

参考代码 /* * @lc app=leetcode id=279 lang=cpp * * [279] Perfect Squares */ // @lc code=start class Solution { public: /* int numSquares(int n) { vector<int> dp(n+1); dp[1] = 1; for (int k=2; k<=n; k++) { int x = sqrt(k); if (x * x == k) { dp[k] = 1; } else { int res = k; // 1 + 1 + 1 + ... for (int i = 1; i <= k/2; i++) { res = min(res, dp[i]+dp[k-i]); } // split into any a+b dp[k] = res; } } return dp[n]; } // O(N^2), TLE, 585/588 cases passed */ int numSquares(int n) { vector<int> dp(n+1); dp[0] = 0; for (int k=1; k<=n; k++) { int x = sqrt(k); if (x * x == k) { dp[k] = 1; } else { int res = k; // 1 + 1 + 1 + ... for (int i=1; i<=x; i++) { res = min(res, 1 + dp[k-i*i]); } // split into i*i+b dp[k] = res; } } return dp[n]; } // O(NlogN), AC }; // @lc code=end O(logN) 数学解法

参考博客 grandyang

前两行代码对算法效率的提升很大,虽然不知道怎么证明这个 ……

class Solution { public: int numSquares(int n) { while (n % 4 == 0) n /= 4; if (n % 8 == 7) return 4; for (int a = 0; a * a <= n; ++a) { int b = sqrt(n - a * a); if (a * a + b * b == n) { return !!a + !!b; } } return 3; } };

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wspfwy.html