问题本质:将一个正整数拆分成至少两个正整数之和,求这些正整数的最大乘积。
方法一:动态规划
定义 $dp[i]$ 表示将正整数 $i$ 拆分成至少两个正整数的和之后,这些正整数的最大乘积。
因为 $0$ 和 $1$ 都不能再分,所以 $dp[0] = dp[1] = 0$。
当 $i \ge 2$ 时,设拆分出的第一个正整数为 $j$($1 \le j \lt i$),此时有以下两种方案:
- 将 $i$ 拆分成 $j$ 和 $i−j$ 的和,且 $i−j$ 不再拆分,此时的乘积是 $j \times (i−j)$ 。
- 将 $i$ 拆分成 $j$ 和 $i−j$ 的和,且 $i−j$ 继续拆分,此时的乘积是 $j \times dp[i-j]$ 。
则 $dp[i]$ 取两种方案的较大值。
总结如下:
-
状态定义:$dp[i]$ 表示将正整数 $i$ 拆分成至少两个正整数之和,这些正整数的最大乘积
-
转移方程:
$$ dp[i] = \max_{1 \le j \lt i} \{ \max \{j \times (i-j), j \times dp[i-j]\} \} $$ -
初始化:$dp[0] = dp[1] = 0$
时空复杂度
- 时间复杂度:$O(n^2)$
- 空间复杂度:$O(n)$
Java 代码
class Solution {
/**
* 方法一:动态规划
* 时间复杂度:O(n^2)
* 空间复杂度:O(n)
*/
public int maxProductAfterCutting(int length) {
if (length < 2) {
return 0;
}
// dp[i] 表示将正整数 i 拆分成至少两个正整数之和,这些正整数的最大乘积
int[] dp = new int[length + 1];
// 0 和 1 都不能拆分,因此 dp[0] = dp[1] = 0
dp[0] = dp[1] = 0;
// i 表示绳子总长度
for (int i = 2; i <= length; i++) {
int curMax = 0;
// j 表示将 i 剪成若干段后,第一段的长度
for (int j = 1; j < i; j++) {
// 当 i >= 2 时,假设对正整数 i 拆分出的第一个正整数是 j(1<=j<i),则有以下两种方案:
// 将 i 拆分成 j 和 i−j 的和,且 i−j 不再拆分成多个正整数,此时的乘积是 j*(i−j)
// 将 i 拆分成 j 和 i−j 的和,且 i−j 继续拆分成多个正整数,此时的乘积是 j*dp[i-j]
int temp = Math.max(j * (i - j), j * dp[i - j]);
curMax = Math.max(curMax, temp);
}
dp[i] = curMax;
}
return dp[length];
}
}
方法二:数学的力量!
结论
- 当 $n=2$ 时,分法唯一,乘积为 $1 \times 1 = 1$。
- 当 $n=3$ 时,乘积最大为 $1 \times 2 = 2$。
- 当 $n = 4$ 时,乘积最大为 $2 \times 2 = 4$。
- 当 $n \gt 4$ 时,应尽可能地多分出 $3$,但是剩下 $4$ 就不再分了,因为 $3\times 1 \lt 4$。
注:以下证明过程来自 整数拆分 - LeetCode官方题解,很严谨很漂亮,这么久不学数学,我写不出这么漂亮的证明,可以学习一下。
证明
基本不等式:
$$ ab \le \frac{(a+b)^2}{4} \quad (a,b \in R^{+},当且仅当a=b时取等号) $$
由基本不等式可知:如果 $x+y$ 的和为定值,那么当且仅当 $x=y$ 时,$xy$ 取得最大值。
具体到本题中,则应该尽可能多地拆分成某个正整数,会使最后的乘积最大。
定义函数 $f(x)$ 表示将正整数 $n$ 拆分成尽可能多的正数 $x$(这里的 $x$ 不一定是整数)情况下的最大乘积,则 $f(x) = x^{\frac{n}{x}}$,求 $f(x)$ 的最大值。
$$
f(x) = x^{\frac{n}{x}} = e^{\frac{n \ln x}{x}}
$$
令 $g(t) = e^t$,$h(x) = \frac{\ln x}{x}$,则 $f(x) = g(n\cdot h(x))$。
因为 $g(t)$ 单调递增,且 $n>0$,所以 $f(x)$ 的单调性与 $h(x)$ 相同。
计算 $h(x)$ 的驻点,即 $h’(x)=\frac{1- \ln x}{x^2}=0$ 的点,得到驻点为 $x=e$。
当 $0\lt x\lt e$ 时 $h’(x)>0$,当 $x>e$ 时 $h’(x)<0$,因此 $x=e$ 是 $h(x)$ 的极大值点,也是 $f(x)$ 的极大值点。由于函数 $f(x)$ 的定义域连续,因此极大值点唯一,也是最大值点。
因此,当 $x=e$ 时,$f(x)$ 取到最大值,$\max f(x)=f(e)=e^{\frac{n}{e}}$。
由于 $e$ 不是整数,因此使用与 $e$ 最接近的整数作为 $x$ 的值,$x$ 可以是 $2$ 或 $3$,此时需要比较 $f(2)$ 与 $f(3)$ 的大小,可以通过计算 $\frac{f(3)}{f(2)}$ 进行比较。
$$
\begin{equation}
\frac{f(3)}{f(2)}
= \frac{e^{n\cdot h(3)}}{e^{n\cdot h(2)}}
= e^{n\cdot h(3)-n\cdot h(2)}
= e^{n\cdot (\frac{\ln 3}{3}-\frac{\ln 2}{2})}
= e^{\frac{n}{6} \cdot (2\ln 3-3\ln 2)}
= e^{\frac{n}{6} \cdot (\ln 9-\ln 8)}
\end{equation}
$$
因为 $\frac{n}{6}(\ln 9-\ln 8) > 0$,所以 $\frac{f(3)}{f(2)} = e^{\frac{n}{6} \cdot (\ln 9-\ln 8)} > 1$,即 $f(3)>f(2)$。
所以当 $x=3$ 时,可以得到最大乘积。因此应该拆分成尽可能多的 $3$。
上述结论适用于 $n>4$ 时的情况,$n\le 4$ 时显而易见,单独讨论一下即可。
时空复杂度
- 时间复杂度:$O(1)$
- 空间复杂度:$O(1)$
Java 代码
class Solution {
/**
* 方法二:数学
*/
public int maxProductAfterCutting(int length) {
if (length <= 3) {
return length - 1;
}
// 除3的商
int quotient = length / 3;
// 除3的余数
int remainder = length % 3;
if (remainder == 0) {
return (int) Math.pow(3, quotient);
} else if (remainder == 1) {
// 余数为1,分到剩下4时不再分
return (int) Math.pow(3, quotient - 1) * 4;
} else {
return (int) Math.pow(3, quotient) * 2;
}
}
}
这才是优质题解!!