给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
1
2
3
| 输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
|
这里比较容易出错的是，必须拆分为至少2个正数，而不能不拆分。
动态规划的解法1
先证明一个结论：数字s拆分为两数之和，两数越接近，乘积越大（或者可以说是，周长相同的矩形，越接近正方形，面积越大）。
1
2
3
4
| a + b = s
设 a = s/2 + p, b = s/2 - p
有 a * b = (s/2+p)(s/2-p) = (1/4)s^2 - p^2
因此 abs(p)越小时，a、b越接近，a*b越大
|
定义 f(n) 为数字n可以拆分至少2个得到的最大乘积：
- 拆分为2个时，最大的乘积是
(n/2) * (n - n/2)。如果n为偶数，两者相等，如果n为奇数，两者相差1。
- 拆分为2个以上，第一个数字选
i 时（ 0 < i < n ），最大乘积为 i * f(n-i)。
因此：
f(n) = max { (n/2)*(n-n/2), 1*f(n-1), ..., (n-1)*f(1) }
初值：
f(1) = 0f(2) = 1 (1 + 1)f(3) = 2 (1 + 2)
于是动态规划解法为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int integerBreak(int n) {
if (n <= 3) return n-1;
int[] dp = new int[n+1];
dp[1] = 0;
dp[2] = 1;
dp[3] = 2;
for (int i = 4; i <= n; ++i) {
dp[i] = i/2 * (i - i/2);
for (int j = 1; j < i; ++j) {
dp[i] = Math.max(dp[i], j * dp[i-j]);
}
}
return dp[n];
}
}
|
动态规划的解法2
证明一个结论：当整数s >= 4时，s拆分为至少2个数字的最大乘积，一定大于等于s（即不拆分）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 设 s = p + q，且p,q均为正整数
求解
pq >= p + q
pq - p - q >= 0
pq - p - q + 1 >= 1
(p-1)(q-1) >= 1
由于 p-1, q-1 均为自然数，因此
p >= 2, q >= 2
于是
s = p + q >= 4
所以当s>=4时，拆分为两个数一定大于等于不拆分
进一步，这两个数还可能继续拆分，使乘积更大
|
定义 f(n) 为数字n拆分得到的最大乘积，而g(n) 为数字n拆分或不拆分得到的最大乘积：
g(n) = max { n, 1*g(n-1), ... (n-1)*g(1) }
当 n >= 4 时，必须要拆分才能得到最大值（等于4时可拆可不拆），因此上式max中的第一项n可以省去，且f(n) = g(n)，于是：
f(n) = g(n) = max { 1*g(n-1), ..., (n-1)*g(1) }
最后使用动态规划实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int integerBreak(int n) {
if (n <= 3) return n-1;
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for (int i = 4; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
dp[i] = Math.max(dp[i], j * dp[i-j]);
}
}
return dp[n];
}
}
|
数学解法
这道题也可以用纯数学解法，性能更好，可参考 题解