Shouyu

Appearance

整数拆分 ​

题目描述 ​

给定一个正整数 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。

题目链接：https://leetcode.cn/problems/integer-break

文章讲解：https://programmercarl.com/0343.整数拆分.html

思路 ​

动态规划的这道题思路是这样的：对于一个正整数 n ，那么拆分出来 k 个数，有一个最大的乘积。无非就是两种情况：

一种是拆出来两个数，这两个数就是乘积最大。假设是 k 和 n-k，那么就是 k*(n -k) 。

另一种情况就是可以拆分出两个以上的数，乘积最大。可以假设为k 和 a ， b 其中a + b = n-k。乘积就是k * a * b。这里隐含了一个子问题：对于n-k这个正整数，最大乘积是 a * b 。所以这种情况下最大乘积就是k* n-k 的最大乘积。

起始就算拆分出了4个数k和 abc， a + b + c = n-k ，abc 也是n-k的最大乘积。

对于每一个k 小于 i 都有这么两种情况。取个最大值即可

动规五部曲 ​

1、dp数组及下标含义 ​

dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积

2.、递归公式 ​

这里需要比较当前dp[i] 是因为要在所有的k的情况下保持一个最大值

C++
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
3、dp数组初始化 ​

因为dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积，下标个正整数是对应的因此dp数组大小需要是n+1

因为第二种情况需要拆分3个数以上，因此需要确定dp[2] = 1;

C++
vector<int> dp(n + 1);
dp[2] = 1;
4、确定遍历顺序 ​

dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

C++
for (int i = 3; i < n + 1; i++) {
        for (int j = 1; j <= i / 2; j++) {
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
        }
    }
5、举例推导 ​

343.整数拆分

代码实现 ​

C++
int integerBreak(int n) {
    // dp[i] 表示将正整数 i 拆分成至少两个正整数的和后，这些整数的最大乘积。
    vector<int> dp(n + 1);
    // 2 只能拆分成 1 + 1，乘积为 1*1 = 1。这是动态规划的起始点。
    dp[2] = 1;
    // 从 i = 3 开始遍历到 n，计算每个 i 的最大乘积
    for (int i = 3; i < n + 1; i++) {
        // j 从 1 遍历到 i/2。
        // 因为 i 拆分成 j 和 (i-j) 与拆分成 (i-j) 和 j 是一样的，
        // 遍历到 i/2 可以避免重复计算，并保证 j <= i-j。
        for (int j = 1; j <= i / 2; j++) {
            // dp[i] = max(当前 dp[i] 的值, max(直接相乘, 拆分一部分后继续拆分))
            // j * (i - j): 表示将 i 拆分为 j 和 (i - j)，直接相乘得到的结果。
            // j * dp[i - j]: 表示将 i 拆分为 j 和 (i - j)，但 (i - j)
            // 可以继续拆分，
            //                 并取 (i - j) 拆分后的最大乘积 (即 dp[i - j])。
            // 比较这两种情况以及当前 dp[i] 的值，取三者中的最大值。
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
        }
    }
    // 返回 n 拆分后的最大乘积
    return dp.back();
}

空间优化 ​

C++