整数拆分

力扣343-整数拆分 (opens new window)

难点：

• 理解dp数组的含义
• 关于递推公式的推导。

本题的第一个难点其实为什么能够使用动态规划来解决？有一个数6，可以被拆分为2+4，而4又可以被拆分为2+2。这里拆分整数6的结果依赖于拆分2和4的结果，下一步的结果依赖于上一步，有这种特点的题目就可以考虑使用动态规划了。 首先定义dp数组的含义：

dp[i]表示拆分数字i能够得到的最大乘积为dp[i]。这个定义很重要，后面推导递推公式的时候如果有疑惑就反过来再看看dp数组的含义！

然后是递推公式，也是本题最令人费解的地方。一个整数可以被拆分为j和i-j，此时的乘积为j * (i - j)，这是将一个整数拆分为两个整数的情况的乘积。如果拆分为多个整数，乘积变为dp[i - j] * j， 如果不理解为什么拆分为多个整数后乘积变为这种形式，建议回看dp数组的含义。所以递推公式为dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j])。多加入的dp[i]是因为只需要dp[i]的最大值。

初始化，应该从2开始初始化，因为只有2开始能被拆分为两个整数。对于j则是从1开始遍历，终止条件 < i - 1。

遍历顺序自然是从后向前遍历。

var integerBreak = function(n) {
    const dp = new Array(n + 1).fill(0)
    //初始化
    dp[2] = 1
    //遍历
    for(let i = 3; i <= n; i++) {
        for(let j = 1; j < i - 1; j++) {
            //递推公式，对应最大值，拆分为两个整数，拆分为多个整数
            dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j])
        }
    }
    return dp[n]
}

本题的核心在于理解递推公式的含义，这是解决本题的关键。