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)``。