0343. Integer Break
===================
题目信息
--------
:题号: 0343
:难度: Medium
:主题: 正整数拆分、乘积最大化、至少两项、返回数值
:原题: `LeetCode 0343 `_
:重点: 各部分必须为正整数、总和必须仍等于 n、至少拆成两项、只返回最大乘积
题目重述
--------
给定整数 ``n``,把它拆分成 ``k`` 个正整数之和,其中 ``k >= 2``。所有拆分项的总和必须恰好等于 ``n``,返回这些整数乘积能够达到的最大值。
``n`` 位于 ``[2, 58]``。即使保持 ``n`` 本身能够得到更大的数值,也不能选择“不拆分”,因为结果必须包含至少两个正整数;题目只要求最大乘积,不要求返回具体拆分方案。
自建示例
--------
拆成三项优于两项:
.. code-block:: text
输入:n = 8
输出:18
解释:拆分为 3+3+2 时乘积为 18,大于 4+4 的乘积 16 以及其他合法拆分。
最小输入:
.. code-block:: text
输入: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++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int integerBreak(int n) {
std::vector 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)``。