题目描述
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 \(k[0],k[1]...k[m - 1]\) 。请问 \(k[0]_k[1]_...*k[m - 1] \)可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 362 <= n <= 58
动态规划
这道题给定一个大于 1 的正整数 n，要求将 n拆分成至少两个正整数的和，并使这些正整数的乘积最大化，返回最大乘积。
解题思路
令 x 是拆分出的第一个正整数，则剩下的部分是 \(n-x\)，\(n-x\)可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。
创建数组 \(\textit{dp}\)，其中\(\textit{dp}[i]\)表示将正整数\(i\)拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 \(\textit{dp}[0]=\textit{dp}[1]=0\)。
当 \(i \ge 2\)时，假设对正整数 i拆分出的第一个正整数是 j（\(1 \le j < i\)），则有以下两种方案：
- 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j \times (i-j)j×(i−j)；
- 将 i 拆分成 j 和 i−j 的和，且 ji−j 继续拆分成多个正整数，此时的乘积是 \(j \times \textit{dp}[i-j]\)。
因此，当 j 固定时，有 \(\textit{dp}[i]=\max(j \times (i-j), j \times \textit{dp}[i-j])\)。由于 j 的取值范围是 1 到 i−1，需要遍历所有的 j 得到 \(\textit{dp}[i]\)的最大值，因此可以得到状态转移方程如下：
\(dp[i]= \mathop{max}\limits_{1≤j<i}\{\mathop{max}(j×(i−j),j×dp[i−j])\}\)
最终得到 \(\textit{dp}[n]\)的值即为将正整数 n拆分成至少两个正整数的和之后，这些正整数的最大乘积。
class Solution {
public:
int cuttingRope(int n) {
vector<int> dp(n+1,1);
for(int i=2;i<=n;++i){
int imax = 0;
for(int j=1;j<i;++j){
int cur = max(j*(i-j),j*dp[i-j]);
if(cur>imax) imax = cur;
}
dp[i] = imax;
}
return dp[n];
}
};复杂度分析
- 时间复杂度：\(O(n^2)\)，其中 n 是给定的正整数。对于从 2 到 n 的每一个整数都要计算对应的 \(\textit{dp}\) 值，计算一个整数对应的 \(\textit{dp}\) 值需要 \(O(n)\) 的时间复杂度，因此总时间复杂度是 \(O(n^2)\)。
- 空间复杂度：\(O(n)\)，其中 \(n\)是给定的正整数。创建一个数组 \(\textit{dp}\)，其长度为 n+1。
数学推导
如果题目改成剑指 Offer 14- II. 剪绳子 II：
2 <= n <= 1000，答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。此时上面方法就行不通了，需要另谋他路。
解题思路
设将长度为 n 的绳子切为 a段：\(n=n_1+n_2+...+n_a\)
本题等价于求解：\(max(n_1×n_2×...×n_a)\)
以下数学推导总体分为两步：① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 3 。
数学推导
以下公式为“算术几何均值不等式” ，等号当且仅当 \(n_1 = n_2 = ... = n_a\)时成立。
\(\frac{n_1+n_2+...n_a}{a} \geq \sqrt[a]{n_1n_2...n_a}\)
推论一： 将绳子 以相等的长度等分为多段 ，得到的乘积最大。
设将绳子按照 x 长度等分为 a 段，即 \(n = ax\)，则乘积为 \(x^a\)。观察以下公式，由于 n 为常数，因此当 \(x^{\frac{1}{x}}\)取最大值时， 乘积达到最大值。
\(x^a = x^{n/x} = (x^{1/x})^n\)
- 根据分析，可将问题转化为求 \(y = x^{\frac{1}{x}}\) 的极大值，因此对 \(x\) 求导数。
\(lny=\frac{1}{x}lnx\) 取对数
\(\frac{1}{y}y^'=\frac{1}{x^2}-\frac{1}{x^2}lnx=\frac{1-lnx}{x^2}\) 对x求导
\(y^'=\frac{1-lnx}{x^2}x^{1/x}\)
令 \(\dot {y} = 0 \)，则 \(1 - \ln x = 0\)，易得驻点为 \(x_0 = e \approx 2.7\)；根据以下公式，可知 \(x_0\)为极大值点。
\(y' \left\{ \begin{aligned} > 0 , && x\in(-\infin,e] \\ <0, && x\in[e,\infin) \end{aligned} \right.\)
由于切分长度 x 必须为整数，最接近 e 的整数为 2 或 3 。如下式所示，代入 \(x = 2\) 和 \(x = 3\) ，得出 \(x = 3\)时，乘积达到最大
\(y(3)=3^{1/3}≈1.44\\ y(2)=2^{1/2}≈1.41\)
这里也可以口算对比方法：给两数字同时取 6 次方，再对比。
推论二： 尽可能将绳子以长度 33 等分为多段时，乘积最大。
- 最优： 3 。把绳子尽可能切为多个长度为 33 的片段，留下的最后一段绳子的长度可能为 0,1,2 三种情况。
- 次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
- 最差： 1 。若最后一段绳子长度为 1 ；则应把一份 3 + 1替换为 2 + 2，因为 \(2 \times 2 > 3 \times 1\)
代码：
大数越界： 当 a增大时，最后返回的 \(3^a\) 大小以指数级别增长，可能超出 int32 甚至 int64 的取值范围，导致返回值错误。
class Solution {
//不用long乘法会溢出
int remainder(int x, int a, int p){
int rem = 1;
long res = x;
while(a>0){
if(a%2==1) rem = (rem*res)%p;
res = (res*res)%p;
a = a/2;
}
return rem;
}
public:
int cuttingRope(int n) {
if(n<=3) return 1*(n-1);
int quotient = n/3;
int rem = n%3;
//不用long乘法会溢出
long res = 1;
// int最多3^(19)
switch(rem){
case 0:
res = remainder(3,quotient,1000000007);break;
case 1:
res = (long)remainder(3,quotient - 1,1000000007)*4;break;
default:
res = (long)remainder(3,quotient,1000000007)*2;
}
return res%(1000000007);
}
};