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

Question

这是我的memory search方法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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); }

这是我的动态规划解法：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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

  非常感谢！