Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example
Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9
LeetCode上的原题，请参见我之前的博客Perfect Squares。
解法一：
class Solution { public: /** * @param n a positive integer * @return an integer */ 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; } };
解法二：
class Solution { public: /** * @param n a positive integer * @return an integer */ int numSquares(int n) { while (n % 4 == 0) n /= 4; if (n % 8 == 7) return 4; vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 0; i < n; ++i) { for (int j = 1; i + j * j <= n; ++j) { dp[i + j * j] = min(dp[i + j * j], dp[i] + 1); } } return dp.back(); } };
解法三：
class Solution { public: /** * @param n a positive integer * @return an integer */ int numSquares(int n) { while (n > 0 && n % 4 == 0) n /= 4; if (n % 8 == 7) return 4; int res = n, i = 2; while (i * i <= n) { int a = n / (i * i), b = n % (i * i); res = min(res, a + numSquares(b)); ++i; } return res; } };
本文转自博客园Grandyang的博客，原文链接：完全平方数[LintCode] Perfect Squares ，如需转载请自行联系原博主。
