343. 整数拆分
题目描述
输入一个正整数 n。把它写成至少两个正整数的和，即 n = a1 + a2 + ... + ak，其中 k >= 2。
在所有拆法中，让这些数的乘积尽量大。返回能得到的最大乘积。
示例 1
输入：n = 2 输出：1
解释：只能拆成 1 + 1，乘积为 1。
示例 2
输入：n = 10 输出：36
解释：拆成 3 + 3 + 4，乘积 3 × 3 × 4 = 36 最大。
数据范围
2 <= n <= 58
解题思路
dp[i] 表示把 i 拆成至少两个数的最大乘积。枚举拆出的第一个数 j，剩下的 i-j 有两种处理：不再拆（乘积 j*(i-j)），或继续拆（乘积 j*dp[i-j]）。取所有 j 与两种方式中的最大值。
为什么正确
计算 dp[i] 时，dp[1..i-1] 都已是最终值。
复杂度分析
时间 O(n^2)，空间 O(n)。
易错点
不能只用 j*dp[i-j]：dp[2]=1、dp[3]=2 比 2、3 本身还小，必须同时考虑“剩下部分不拆”的 j*(i-j)。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
return dp[n]class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
return dp[n];
}
}class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1, 0);
dp[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
dp[i] = max({dp[i], j * (i - j), j * dp[i - j]});
return dp[n];
}
};func integerBreak(n int) int {
dp := make([]int, n+1)
dp[1] = 1
for i := 2; i <= n; i++ {
for j := 1; j < i; j++ {
dp[i] = max(dp[i], j*(i-j), j*dp[i-j])
}
}
return dp[n]
}var integerBreak = function(n) {
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
for (let i = 2; i <= n; i++)
for (let j = 1; j < i; j++)
dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]);
return dp[n];
};function integerBreak(n: number): number {
const dp: number[] = new Array(n + 1).fill(0);
dp[1] = 1;
for (let i = 2; i <= n; i++)
for (let j = 1; j < i; j++)
dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]);
return dp[n];
}其他解法
动态规划逐一枚举第一段的长度，通用但是 O(n²)；数学做法直接得出最优拆分的结构，O(1)。
解法 2：数学（尽量拆出 3） 时间 O(1)，空间 O(1)
可以证明：拆出的因子只用 2 和 3，并且 3 越多越好。2 和 3 必须拆成 1 加一个数，分别返回 1 和 2。否则看 n 除以 3 的余数：余 0 就是 3 的 n/3 次方；余 1 时把一个 3+1 改成 2+2，得到 3 的 (n/3-1) 次方乘 4；余 2 就是 3 的 n/3 次方乘 2。
常数时间，代码很短。但正确性依赖数学证明（大于 4 的因子必然可以再拆以增大乘积，而 3×3 > 2×2×2），面试时不容易当场论证，也不容易推广到其他限制条件。
class Solution:
def integerBreak(self, n: int) -> int:
if n <= 3:
return n - 1
q, r = divmod(n, 3)
if r == 0:
return 3 ** q
if r == 1:
return 3 ** (q - 1) * 4
return 3 ** q * 2class Solution {
public int integerBreak(int n) {
if (n <= 3) return n - 1;
int q = n / 3, r = n % 3;
if (r == 0) return (int) Math.pow(3, q);
if (r == 1) return (int) Math.pow(3, q - 1) * 4;
return (int) Math.pow(3, q) * 2;
}
}class Solution {
public:
int integerBreak(int n) {
if (n <= 3) return n - 1;
int q = n / 3, r = n % 3;
if (r == 0) return (int)pow(3, q);
if (r == 1) return (int)pow(3, q - 1) * 4;
return (int)pow(3, q) * 2;
}
};func integerBreak(n int) int {
if n <= 3 {
return n - 1
}
q, r := n/3, n%3
pow3 := func(k int) int {
res := 1
for ; k > 0; k-- {
res *= 3
}
return res
}
if r == 0 {
return pow3(q)
}
if r == 1 {
return pow3(q-1) * 4
}
return pow3(q) * 2
}var integerBreak = function(n) {
if (n <= 3) return n - 1;
const q = Math.floor(n / 3), r = n % 3;
if (r === 0) return 3 ** q;
if (r === 1) return 3 ** (q - 1) * 4;
return 3 ** q * 2;
};function integerBreak(n: number): number {
if (n <= 3) return n - 1;
const q = Math.floor(n / 3), r = n % 3;
if (r === 0) return 3 ** q;
if (r === 1) return 3 ** (q - 1) * 4;
return 3 ** q * 2;
}