1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i < j * j) {
                    break;
                }
                dp[i] = Math.min(dp[i], dp[i - (j * j)] + 1);
            }
        }
        return dp[n];
    }
}

这道题的intution就是凑n的话. 我们有1, 4, 9, 16…一直到某个平方数小于n, 一共这些数字可以选. 那么这样的话, 我们可以让每个数字都是最后一个数. 然后看少了它们后剩下的数字凑最小是多少. 比如是n的话, 我们看n - 1最少需要几个数, 这个答案 + 1(最后补上一个1凑够n)即可. 同理看凑n - 4最少需要几个数, 这个答案 + 1(最后补上一个4凑够n即可)即可. 我们把所有的候选数字都走一遍, 看哪个最小, 那就是答案. 但是问题就是我们的候选数字一定是小于n的平方数. 那么为了算n - 1最少需要多少数字凑够, 我们就需要知道比n - 1小的平方数有哪些, 这样知道凑n - 1的候选人都有谁, 然后挨个按照我们之前写的逻辑再走一遍. 这样的话就很花费时间.

于是我们不写recursion + memoization, 直接开始DP. 通过上面的讨论, dp的逻辑就是把要凑的数挨个减去自己的候选人, 然后看剩下的数中能凑齐的最小值是多少, 这个值 + 1就是凑当前数的最小值. 那么当前数就需要之前数字(小于自己数字)的状态(它们凑的最少数字个数). 我们于是从base case开始, dp[0]是多少呢? 也就是凑0最少需要几个数字呢? 按照我们的逻辑, 我们挑一个数字试一下, 比如1, 1的话凑1的候选人只有1, 因为小于等于1的平方数只有1. 此时我们就需要知道凑0最少需要几个数, 这样我们在这个答案之上+ 1就是凑1的最少数. 我们知道凑1的最少数是1. 那么为了满足我们的状态转移方程, 我们让dp[0] = 0就满足我们的方程. 此时1会看dp[0]是多少, 发现是0, 那么这个值+ 1就是dp[1]的答案, 这个答案也是正确的, 于是dp[0]的值确定. 然后我们就可以开始了. 对于一个数字, 我们要走遍它的候选人. 这也就是第7行这个循环干的事情. 先看凑i - 1的平方最小是多少, 再看凑i - 2的平方最小是多少, 一直到看凑i - j的平方最小是多少, j的平方最大就是i, 如果超过i, j就不是候选人了.

时间复杂度: O(n * 根号n) 因为候选人最多是根号n个, 我们要循环n次, 因此big O就是它.
空间复杂度: O(n) 因为我们用了一个dp数组.