LeetCode343 疑问

Question

memo[i] = max3(memo[i], j * (i - j), j * memo[i - j]);

同样是这句话，分成2部分即以上的情况 j * memo[i - j])，为什么不是 这样的：

情况1: j * memo[i - j])

情况2: memo[i] * (i - j)

情况3: memo[i] * memo[i - j]

举个实际的例子：

我想到的递归方程 时间超过5%
dp[i] = Math.max(dp[i], Math.max(j * (i - j), Math.max(j * dp[i - j], dp[j] * dp[i - j])));
老师的递归方程： 超过100%
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));

j虽然是循环的变量，但j也存在可拆分的情况。为什么只考虑情况1就能覆盖其他2中情况呢？还是说其他两种情况被已经覆盖在memo[i], j * (i - j) 这两种情况里了？有点绕不过来。我的似乎更好理解，但为什么不考虑 memo[i] * memo[i - j]也是正确的呢？

我的想出来的完整的代码：

 public int integerBreakDP(int n) {
        int[] memo = new int[n + 1];
        memo[1] = 1;
        memo[2] = 1;

        for (int i = 3; i < n; i++) {
            for (int j = 1; j < i; j++) {
                memo[i] = Math.max(max3(j * (i - j), i * memo[i - j], memo[i]),memo[j] * memo[i - j]);
            }
        }
        return memo[n];
    }

Answer 1

liuyubobobo 2023-08-21 15:43:38

我理解你的问题和这个问题是一致的，可以参考：https://coding.imooc.com/learn/questiondetail/GjNdEXKpjRy69rn4.html

（如果问题不一致，请再补充提问告诉我一下，谢谢！）

继续加油！：）

• 提问者 慕妹2978617 #1

  非常感谢！