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

综合以上分析,可以写出如下的代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注