LeetCode-279-Perfect Squares

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

综合以上分析，可以写出如下的代码：