又是一道非常典型的动态规划的题目。这道题的题意是：给定一个正整数n，那么总可以有若干个完全平方数之和等于n，求出最少的个数。如 n = 12, 12 = 4 + 4 + 4，因此返回3。又如 n = 13, 13 = 4 + 9，因此返回2。
思路：生成一个长度为 n+1的数组 dp。dp[i] (0 <= i <= n)表示若干个完全平方数之和等于 i 的最小个数。我们可以通过举例子来寻找一些规律：
- n = 0，和等于0的完全平方数不存在，因此 dp[0] = 0；
- n = 1，和等于1的完全平方数只要1一个，因此 dp[1] = 1；
- n = 2，和等于2的完全平方数分别是1和1，因此 dp[2] = 2，即 dp[2] = 1 + dp[2 – 1 * 1]；
- n = 3，和等于3的完全平方数是1和1和1，因此 dp[3] = 3，即 dp[3] = 1 + dp[3 – 1 * 1]；
- n = 4，和等于4的完全平方数是4，因此 dp[4] = 1；
- n = 5，和等于5的完全平方数是4和1，因此 dp[5] = 2，即 dp[5] = 1 + dp[5 – 2 * 2]；
- n = 6, 和等于6的完全平方数是4和1和1，因此 dp[6] = 3，即 dp[6] = 1 + dp[4]；
因此有 dp[i] = 1 + dp[i - j*j],(j * j <= i, j >= 1)。但是我们也要注意到一些特殊情况，比如题目例子中给的12，12 / (2*2) = 3，所以 dp[i] = i / (j*j), (i % (j * j) == 0。
综合以上分析，可以写出如下的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: int numSquares(int n) { vector<int> dp(n + 1); if (n < 0) { return 0; } dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = INT_MAX; for (int j = 1; j * j <= i; j++) { if (i % (j * j) == 0) { dp[i] = fmin(dp[i], i / (j * j)); } else { dp[i] = fmin(dp[i], 1 + dp[i - j * j]); } } } return dp[n]; } }; |