343. 整数拆分
#动态规划 2025-01-24 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        int left, right;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= (i / 2); j++) {
                left = max(j, dp[j]);
                right = max(i - j, dp[i - j]);
                dp[i] = max(dp[i], left * right);
            }
        }
        return dp[n];
    }
};

一个数有机会拆分成多个组合，0 和 1 没有拆分意义，结果为 0。

拆分从 1 开始，截止到 n / 2，因为再往后就只是重复行为，故而拆分范围为[1,n / 2]。

dp 记录的是这个数拆分之后的最大值，我们在每次循环中，把一个数拆分成 j 和 i - j，然后依次求出 j 和 dp[j] 的最大值 left， i - j 和 dp[i - j] 的最大值 right。

left 和 right 相乘，把这个结果与当前 dp[i] 比较取得最大值，并存储到 dp[i] 中，等到这次循环结束，就彻底得到 dp[i] 的最大值了。

 

1
2
3
left = max(j, dp[j]);
right = max(i - j, dp[i - j]);
dp[i] = max(dp[i], left * right);

这样一个行为，就把这些情况都考虑进去了：j * (i - j) 、dp[j] * dp[i - j]、j * dp[i - j]、dp[j] * (i - j)，求这四种情况的最大值。