0343. Integer Break¶
题目信息¶
- 题号:
0343
- 难度:
Medium
- 主题:
正整数拆分、乘积最大化、至少两项、返回数值
- 原题:
- 重点:
各部分必须为正整数、总和必须仍等于 n、至少拆成两项、只返回最大乘积
题目重述¶
给定整数 n,把它拆分成 k 个正整数之和,其中 k >= 2。所有拆分项的总和必须恰好等于 n,返回这些整数乘积能够达到的最大值。
n 位于 [2, 58]。即使保持 n 本身能够得到更大的数值,也不能选择“不拆分”,因为结果必须包含至少两个正整数;题目只要求最大乘积,不要求返回具体拆分方案。
自建示例¶
拆成三项优于两项:
输入:n = 8
输出:18
解释:拆分为 3+3+2 时乘积为 18,大于 4+4 的乘积 16 以及其他合法拆分。
最小输入:
输入:n = 2
输出:1
解释:必须至少拆成两个正整数,唯一拆分是 1+1,乘积为 1。
状态明确表达“必须继续拆分”¶
令 dp[x] 表示把 x 拆分后能得到的最大乘积。枚举第一段 first,剩余部分为 rest = x - first:可以把剩余部分整体作为一段,得到 first * rest;也可以继续使用 dp[rest],得到 first * dp[rest]。两者取大,就同时覆盖了“最后一刀”和“继续拆分”两种情况。
dp[1] = 1 只是为了让它作为递归中的一段数参与 2 = 1 + 1;真正返回的 n 从 2 开始,所以不会把“不拆分 n”当作答案。按 x 从小到大填表,所有 rest < x 的状态都已经计算完成。
C++ 实现¶
class Solution {
public:
int integerBreak(int n) {
std::vector<int> dp(n + 1, 0);
dp[1] = 1;
for (int value = 2; value <= n; ++value) {
for (int first = 1; first < value; ++first) {
int rest = value - first;
dp[value] = std::max(
dp[value],
std::max(first * rest, first * dp[rest]));
}
}
return dp[n];
}
};
代码分析¶
每个拆分方案都有第一段,剩余部分要么整体保留、要么继续拆分,转移覆盖且不重复遗漏;交换第一段和剩余段不会影响枚举完整性。状态数为 O(n),每个状态枚举 O(n) 个第一段,时间复杂度为 O(n^2),额外空间为 O(n)。