279. Perfect Squares

Leetcode Math Dynamic Programming Breath-first Search

Given a positive integer $n$, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to $n$.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

分析

考查基本的动态规划。这道题目解法有很多种，但是最直接、最快的方法是动态规划。当我们寻找和为12的平方数时，假如找到了3的平方等于9， 那么再找一下和为12-9=3的平方数，然后发现是三个1，也就是说一共有4个。顺着这个思路，

dp[1] = dp[0] + dp[1] = 1
dp[2] = dp[1] + dp[1] = 2
dp[3] = dp[2] + dp[1] = 3
dp[4] = Min{ dp[4-1*1]+dp[1], dp[4-2*2]+dp[4] } 
      = Min{ dp[3]+1, dp[0]+dp[4] } 
      = 1               
dp[5] = Min{ dp[5-1*1]+dp[1], dp[5-2*2]+dp[4] } 
      = Min{ dp[4]+1, dp[1]+1 } 
      = 2

OK，还有一个特殊情况要处理一下，例如dp[4] = d[0] + dp[4]，把dp[0]定义为1，那么所有的平方数都为1，符合题目要求。下面给出完整代码：

public int numSquares(int n) {
    if (n < 1) return 0;
    int [] dp = new int[n + 1];
    dp[0] = 1; dp[1]  = 1;
    for (int i = 2; i <= n; i++) {
        int min = i, s = 1;
        for (int j = 1; s <= i; j++, s = j * j)
            min = Math.min(min, dp[s] + dp[i-s]);
        dp[i] = min;
     }
    return dp[n];
}

内循环的时间复杂度是$O(\log n)$,外循环的时间复杂度是$O(n)$，所以时间复杂度是$O(n\log n)$。但是实际上dp[s=j*j]肯定等于1，因为s是一个平方数，所以可以简化为

public int numSquares(int n) {
    if (n < 1) return 0;
    int [] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int min = i, s = 1;
        for (int j = 1; j *j <= i; j++, s = j * j)
            min = Math.min(min, 1 + dp[i-s]);
        dp[i] = min;
     }
    return dp[n];
}

一种巧妙的方法是把dp设置为静态变量，在多次调用时，将计算过的值立即返回。

private List<Integer> list = new ArrayList<>(Collections.singletonList(0));
public int numSquares(int n) {
    if (n < 1) return 0;
    if (n < list.size()) return list.get(n);
    for (int i = list.size(); i <= n; i++) {
        int min = i, s = 1;
        list.add(0);
        for (int j = 1; s <= i; j++, s = j * j)
            min = Math.min(min, 1 + list.get(i-s));
        list.set(i, min);
     }
    return list.get(n);
}