leetCode 343.整数拆分 动态规划

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

>>动规五部曲

1.确定dp数组（dp table）以及下标的定义

• dp[i]: 分拆数字i,可以得到的最大乘积为 dp[i]
• dp[i] 的定义将贯彻整个解题过程

2.确定递推公式

 【思考🤔】如何得到上图这种拆分的结果呢？

详细分析：
dp[3] = max(dp[3],max((3-1)*1,dp[(3-1)] * 1)) = 2
 
dp[4] = max(dp[4],max((4-1)*1,dp[(4-1)] * 1)) = 3
dp[4] = max(dp[4],max((4-2)*2,dp[(4-2)] * 2)) = 4
 
dp[5] = max(dp[5],max((5-1)*1,dp[(5-1)] * 1)) = 4
dp[5] = max(dp[5],max((5-2)*2,dp[(5-2)] * 2)) = 6
dp[5] = max(dp[5],max((5-3)*3,dp[(5-3)] * 3)) = 6
 
dp[6] = max(dp[6],max((6-1)*1,dp[(6-1)] * 1)) = 6
dp[6] = max(dp[6],max((6-2)*2,dp[(6-2)] * 2)) = 8
dp[6] = max(dp[6],max((6-3)*3,dp[(6-3)] * 3)) = 9
dp[6] = max(dp[6],max((6-4)*4,dp[(6-4)] * 4)) = 9
 
dp[7] = max(dp[7],max((7-1)*1,dp[(7-1)] * 1)) = 9
dp[7] = max(dp[7],max((7-2)*2,dp[(7-2)] * 2)) = 12
dp[7] = max(dp[7],max((7-3)*3,dp[(7-3)] * 3)) = 12
dp[7] = max(dp[7],max((7-4)*4,dp[(7-4)] * 4)) = 12
dp[7] = max(dp[7],max((7-5)*5,dp[(7-5)] * 5)) = 12
 
dp[8] = max(dp[8],max((8-1)*1,dp[(8-1)] * 1)) = 12
dp[8] = max(dp[8],max((8-2)*2,dp[(8-2)] * 2)) = 18
dp[8] = max(dp[8],max((8-3)*3,dp[(8-3)] * 3)) = 18
dp[8] = max(dp[8],max((8-4)*4,dp[(8-4)] * 4)) = 18
dp[8] = max(dp[8],max((8-5)*5,dp[(8-5)] * 5)) = 18
dp[8] = max(dp[8],max((8-6)*6,dp[(8-6)] * 6)) = 18
 
dp[9] = max(dp[9],max((9-1)*1,dp[(9-1)] * 1)) = 18
dp[9] = max(dp[9],max((9-2)*2,dp[(9-2)] * 2)) = 24
dp[9] = max(dp[9],max((9-3)*3,dp[(9-3)] * 3)) = 27
dp[9] = max(dp[9],max((9-4)*4,dp[(9-4)] * 4)) = 27
dp[9] = max(dp[9],max((9-5)*5,dp[(9-5)] * 5)) = 27
dp[9] = max(dp[9],max((9-6)*6,dp[(9-6)] * 6)) = 27
dp[9] = max(dp[9],max((9-7)*7,dp[(9-7)] * 7)) = 27
 
dp[10] = max(dp[10],max((10-1)*1,dp[(10-1)] * 1)) = 27
dp[10] = max(dp[10],max((10-2)*2,dp[(10-2)] * 2)) = 27
dp[10] = max(dp[10],max((10-3)*3,dp[(10-3)] * 3)) = 36
dp[10] = max(dp[10],max((10-4)*4,dp[(10-4)] * 4)) = 36
dp[10] = max(dp[10],max((10-5)*5,dp[(10-5)] * 5)) = 36
dp[10] = max(dp[10],max((10-6)*6,dp[(10-6)] * 6)) = 36
dp[10] = max(dp[10],max((10-7)*7,dp[(10-7)] * 7)) = 36
dp[10] = max(dp[10],max((10-8)*8,dp[(10-8)] * 8)) = 36

动态递推公式： dp[i] = max(dp[i],max((i - j) * j,dp[i - j] * j));

3.dp数组的初始化

dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1

4.确定遍历顺序

遍历顺序为： 

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j < i - 1; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

注意：为什么 j=1；j < i - 1，因为dp[0] = 0,dp[1] = 0，所以无需拆分出 数字 0 或者 1，这对于求最大乘积是没有意义了！！！

j 的结束条件是 j < i - 1 ，其实 j < i 也是可以的，不过可以节省一步，例如让j = i - 1，的话，其实在 j = 1的时候，这一步就已经拆出来了，重复计算，所以 j < i - 1

 >>进一步优化

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j <= i / 2; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

来自代码随想录的解释：代码随想录 (programmercarl.com)

因为拆分一个数n 使乘积最大，那么一定是拆分成 m 个近似相同的子数相乘才是最大的

例如 6 拆成 3 x 3，10 拆成 3 x 3 x 4。 100 的话 也是拆成 m 个近似数组的子数 相乘才是最大的。只不过我们不知道 m 究竟是多少而已，但是可以明确的是 m 一定 大于等于2，既然 m 大于等于 2 ，也就是 最差也应该是拆成两个相同的 可能是最大值。

那么 j 遍历，只需要遍历到 n / 2就可以，后面就没有必要遍历了，一定不是最大值

5.举例推导dp数组

 

// leetCode 343.整数拆分
class Solution {
public:
    // 动态规划 
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[2] = 1;
        for(int i = 3;i <= n;i++) {
            for(int j = 1;j < i-1;j++) {
                dp[i] = max(dp[i],max((i-j)*j,dp[i-j]*j));
            }
        }
        return dp[n];
    }
 
    // 动态规划 + 优化
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[2] = 1;
        for(int i = 3;i <= n;i++) {
            for(int j = 1;j <= i / 2;j++) {
                dp[i] = max(dp[i],max((i-j)*j,dp[i-j]*j));
            }
        }
        return dp[n];
    }
};
 
 

• 时间复杂度:O(n^2)
• 空间复杂度:O(n)

有贪心算法的解法，后续填坑~🕳

来自代码随想录课堂截图：

参考和推荐文章：

代码随想录 (programmercarl.com)

动态规划，本题关键在于理解递推公式！| LeetCode：343. 整数拆分_哔哩哔哩_bilibili