# 题目
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
# 分析
动态规划五部曲
1 确定 dp 数组及下标的含义
dp [i]：分拆数字 i，得到最大乘积和 dp [i]
2 确定递推公式
dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
3 dp 的初始化
dp[2] = 1
4 确定遍历顺序
dp [i] 是依靠 dp [i - j] 的状态，所以遍历 i 一定是从前向后遍历，先有 dp [i - j] 再有 dp [i]。
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)); | |
} | |
} |
5 举例推导 dp 数组
。。。。
完整代码
// 时间复杂度：O (n^2) | |
// 空间复杂度：O (n) | |
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 / 2; j++) { | |
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)); | |
} | |
} | |
return dp[n]; | |
} | |
}; |
