题目链接：343. 整数拆分

动态规划

(1) 确定 dpdpdp 数组下标含义：
dp[i]dp[i]dp[i]: 将 iii 拆分为至少两个正整数之后的最大乘积；
(2) 确定递推公式：
当 i≥2i \ge 2i≥2 时,
设 jjj 是 iii 拆分出来的第一个正整数，(1≤j≤i−11\leq j \leq i - 11≤j≤i−1)，有以下两种方案:
i−ji - ji−j 不再拆分, 乘积为 j∗(i−j)j * (i - j)j∗(i−j);
i−ji - ji−j 继续拆分，乘积为 j∗dp[i−j]j * dp[i - j]j∗dp[i−j];
需要遍历所有 jjj 得到 dp[i]dp[i]dp[i], 因此
dp[i]=max(dp[i],max(j∗(i−j),j∗dp[i−j]));dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));dp[i]=max(dp[i],max(j∗(i−j),j∗dp[i−j]));
(3) dpdpdp 数组初始化：
111 是最小的正整数, 不能拆分, 所以 dp[1]=0dp[1] = 0dp[1]=0; 其他下标均初始化为 000。
(4) 遍历顺序：
外循环 iii : 2−n2 - n2−n, 内循环 jjj : 1−(n−1)1 - (n - 1)1−(n−1), 从小到大。
(5) 举例推导 dpdpdp 数组：
n=6n = 6n=6 时:

dp[6]=9dp[6] = 9dp[6]=9 即为最终结果。

代码如下：

class Solution {
public:int integerBreak(int n) {vector dp(n + 1, 0);dp[1] = 0;for (int i = 2; i <= n; i++) {for (int j = 1; j <= i - 1; j++) {dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));}}return dp[n];}
};