LeetCode【279】完全平方数

题目：

思路：
https://www.acwing.com/solution/leetcode/content/114877/

1、给定数字，是由若干个完全平方数组合而成，求使用的最小的完全平方数的个数，如果这些完全平方数已知，则完全等同于百元百鸡问题。

2、DP问题要有一个dp数组，保存着局部子dp结果。

代码：

    public static int numSquares(int n) {
        int[] dp = new int[n + 1];
        final int INF = n + 1;
        // Arrays.fill(dp, n + 1);   // 这里不可以提前初始化，因为会影响计算dp[0],dp[1]开始得值

        for (int i = 1; i <= n; ++i) {
            dp[i] = INF;         // 这里给出个不可能产生的较大值，
            for (int j = 1; j <= i / j; ++j) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);    // dp问题要注意dp的初始值，也就是dp[0] dp[1]
            }
        }
        return dp[n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

注：此题代码行数很少，但是解题思路很巧妙复杂。