LC343题解 | #整数拆分#

动态规划

动归三部曲：

dp[i] 是啥？ dp[i] 表示的是数字 i 所拥有的最大乘积

dp[i] 的递推公式？dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j])); 下面会有解释

dp[i] 的初始化？ 我们只需要初始化dp[2]，从3开始遍历即可，因为dp[1] 和dp[0] 没有意义

为什么递推公式是这样的？

因为dp[i]只要放i的最大乘积即可，因此max取一个dp[i]。

内层max表示的是：两个数的乘积和多个数的乘积取max。

两个数的乘积为当前的因子j和(i-j)，

多个数的没法直接求，因为不好控制具体几个因子，所以交给前一位dp[i-1]。

证明：i = 1 + (i-1)，所以dp[i] = 1 * dp[i-1]

则有：i = j + (i-j)，所以dp[i] = j * dp[i-j]

dp[i] = 1 * dp[i-1]只是一个特例

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1]; // dp[i]表示数字i的最大乘积
        // 为什么是n+1，因为长度为n只能求到dp[0]~dp[n-1]，所以要加一位才能求到dp[n]
        dp[2] = 1;  // 题干给的初始化，从2开始
        for (int i = 3; i <= n; ++i) {      // 从dp[3]开始遍历，向后填充直到dp[n]
            // 分解i的第一个因子，到i-j结束，多了就重复了
            for (int j = 1; j <= i-j; ++j) {
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
            }
        }
        return dp[n];
    }
}