这是我的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]?

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

谢谢老师！