一、题目描述
给你一根长度为 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。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 1000
二、题目解析
这道题目在 剑指 Offer 14- I. 剪绳子 的基础上增加了一个限制：需要取模操作。
理论上也是可以在 剑指 Offer 14- I. 剪绳子 基础上同样使用动态规划进行处理，代码只需要修改几行就行，先看代码：
import java.math.BigInteger;
class Solution {
public int cuttingRope(int n) {
// 长度为 1 的绳子没法剪了
if ( n <= 1 ) return 1;
// 用一个名为 dp 的数组来记录从 0 到 n 长度的绳子剪掉后的最大乘积
// 默认都是 0
BigInteger[] dp = new BigInteger[n + 1];
Arrays.fill(dp, BigInteger.valueOf(1));
// 由于绳子必须被剪，所以长度为 2 的绳子只有剪成 1 和 1 的两段，乘积结果为 1
// dp[2] = 1;
// 长度大于等于 3 的绳子才开始进入我们的讨论范围
// 从长度为 3 的绳子开始考虑，讨论它的最大乘积是多少，并不断的延伸绳子的长度
for(int i = 3; i < n + 1; i++){
// 对于长度为 i 的绳子，它可以分为两个区间 j 和 i - j
// j 的范围由 2 开始，因为剪长度为 1 的绳子无法扩大乘积的值
// j 的范围可以延伸至 i - 1
for(int j = 2; j < i; j++){
// 不剪总长度乘积为 j * （ i - j）
// 剪的话长度乘积为 j * dp[ i - j ]
// 取两者的最大值，即 Max ( j * ( i - j) , j * dp[ i - j] )
// 那么此时 dp[i] 的值取 i 不剪的值（ dp[i]) 和剪的值 Math.max(j * (i - j), j * dp[i - j]) 这两者的最大值
// 比如一开始 i = 3 ， j = 2
// dp[3] = Math.max( 0 ,Math.max ( 2 * 1, 2 * dp[1])
// = Math.max( 0 ,Math.max ( 2, 2))
// = 2
dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j))).max(dp[i - j].multiply(BigInteger.valueOf(j)));
}
}
return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
}
}
如果将这个代码提交，虽然可以通过，但可以看出效率还是比较低的。
这道题目的最好解法是使用贪心算法。
核心点在于尽可能把绳子分成长度为 3 的小段，这样乘积最大。
这个结论可以通过数学来证明。具体证明容我后面补充。
依托于这个结论，可以这样设计思路。
- 1、当绳子长度为 2 时，由于只可能剪成长度为 1 的两段，所以最大乘积为 1
- 2、当绳子长度为 3 时，可以剪成长度为 1 和长度为 2 的两段，所以最大乘积为 2
- 3、当绳子长度为 4 时，可以剪成长度为 2 和长度为 2 的两段，所以最大乘积为 4
- 4、当绳子长度大于了 4 时，总是尽可能的去尝试剪出更多的长度为 3 的绳子，那么操作就是每次循环绳子的操作，每次循环都将绳子长度 n 减去 3，乘积 res 乘以 3 再取模，直到绳子的长度为 1 、2 、3 这三种长度之间的任意一种
- 5、循环结束时，再将 res 与剩下的绳子长度 n 进行相乘再取模
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public int cuttingRope(int n) {
// 1、当绳子长度为 2 时，由于只可能剪成长度为 1 的两段，所以最大乘积为 1
if( n == 2 ) return 1;
// 2、当绳子长度为 3 时，可以剪成长度为 1 和长度为 2 的两段，所以最大乘积为 2
if( n == 3 ) return 2;
// 注意 res 的类型
long res = 1;
// 当绳子长度大于了 4 时，总是尽可能的去尝试剪出更多的长度为 3 的绳子
// 那么操作就是每次循环绳子的操作，每次循环都将绳子长度 n 减去 3，乘积 res 乘以 3 再取模
// 直到绳子的长度为 1 、2 、3 这三种长度之间的任意一种
while(n > 4){
res = res * 3 % 1000000007;
n -= 3;
}
// 由于题目需要返回 int 型，所以强转一下
return (int) (res * n % 1000000007);
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public:
int cuttingRope(int n) {
// 1、当绳子长度为 2 时，由于只可能剪成长度为 1 的两段，所以最大乘积为 1
if( n == 2 ) return 1;
// 2、当绳子长度为 3 时，可以剪成长度为 1 和长度为 2 的两段，所以最大乘积为 2
if( n == 3 ) return 2;
// 注意 res 的类型
long res = 1;
// 当绳子长度大于了 4 时，总是尽可能的去尝试剪出更多的长度为 3 的绳子
// 那么操作就是每次循环绳子的操作，每次循环都将绳子长度 n 减去 3，乘积 res 乘以 3 再取模
// 直到绳子的长度为 1 、2 、3 这三种长度之间的任意一种
while(n > 4){
res = res * 3 % 1000000007;
n -= 3;
}
// 由于题目需要返回 int 型，所以强转一下
return (int) (res * n % 1000000007);
}
};
3、Python 代码
class Solution:
def cuttingRope(self, n: int) -> int:
# 1、当绳子长度为 2 时，由于只可能剪成长度为 1 的两段，所以最大乘积为 1
if n == 2 : return 1
# 2、当绳子长度为 3 时，可以剪成长度为 1 和长度为 2 的两段，所以最大乘积为 2
if n == 3 : return 2
# 注意 res 的类型
res = 1
# 当绳子长度大于了 4 时，总是尽可能的去尝试剪出更多的长度为 3 的绳子
# 那么操作就是每次循环绳子的操作，每次循环都将绳子长度 n 减去 3，乘积 res 乘以 3 再取模
# 直到绳子的长度为 1 、2 、3 这三种长度之间的任意一种
while n > 4 :
res = res * 3 % 1000000007
n -= 3
# 由于题目需要返回 int 型，所以强转一下
# Python 就直接用就行
return res * n % 1000000007
