leetcode 279我的动态规划解法会超时，老师可以帮我看看吗？

Question

这是我的memory search方法

private int[] memo;

private int recursionNumSquares(int n){

    if(memo[n] == 0){
        memo[n] = Integer.MAX_VALUE;
        for(int i = 1; i < n; i ++){
            if(i * i == n){
                memo[n] = 1;
                break;
            }
            else{
                memo[n] = Math.min(memo[n],recursionNumSquares(i)+recursionNumSquares(n-i));
            }
        }
    }

    return memo[n];
}

public int numSquares(int n) {

    memo = new int[n + 1];
    memo[1] = 1;

    return recursionNumSquares(n);
}

这是我的动态规划解法：

public int numSquares(int n) {

    int[] memo = new int[n + 1];
    Arrays.fill(memo, Integer.MAX_VALUE);
    memo[1] = 1;

    for(int i = 2; i <= n; i ++){
        for(int j = 1; j < i; j ++){
            if(j * j == i){
                memo[i] = 1;
                break;
            }
            else
                memo[i] = Math.min(memo[i], memo[j]+memo[i-j]);
        }
    }

    return memo[n];
}

原因似乎是因为我使用了memo[i] = Math.min(memo[i], memo[j]+memo[i-j]), 而不是memo[i] = Math.min(memo[i], 1+memo[i-j * j])

我的问题是，我们似乎无法知道memo[i]一定就是1+memo[i - j*j]，为什么不进行遍历，而是直接跳过很多值，选择了memo[i -j*j]?

我的解法结果是对的，只是超时了，这是截图：

谢谢老师！

Answer 1

liuyubobobo 2018-04-24 10:20:21

我只看了一下你的记忆化搜索的逻辑。你的方式相当于对每一个数字n，将他所有的拆分都尝试一遍，比如对于5，会递归下去尝试1+4; 2+3; 3+2; 4+1四种情况。

首先，具有对称性，我们只看1+4; 2+3就好了。

其次，是最最重要的，在递归尝试2 + 3之前，我们就可以看到2不是一个完全平方数，所有这种情况根本不需要递归下去尝试：）

这里，我给出的参考代码，对于k，下一步去看k - i*i就好了，就是这个意思。对于每一个数字k，直接去看这个数字k减去另一个完全平方数以后的结果。看完k-1，直接去看k-4，因为k-3的意思就是要用数字3区拼这个k，但我们已经知道数字3肯定不是完全平方数了：）

我的参考代码Java版：https://github.com/liuyubobobo/Play-Leetcode/tree/master/0279-Perfect-Squares/java-0279/src

• 提问者 想不出来叫什么 #1

  是否有可能有这种情况：
  k可以分解为k-i和i，k的完全平方和数为7，而k-i是3，i是2，虽然i不是完全平方数，但是分解为k-i和i之后，完全平方数变少了。所以只看k-i*i和i*i，会不会有遗漏的情况？

• liuyubobobo 回复 提问者 想不出来叫什么 #2

  1）题目要求把一个数分解为完全平方数的和；2）所以在尝试的时候，从小到大尝试：1，4，9，....。只要尝试了1，就不会遗漏：）

• 提问者 想不出来叫什么 #3

  非常感谢！