又是一道非常典型的动态规划的题目。这道题的题意是:给定一个正整数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]; } }; |