剑指 Offer 14- I. 剪绳子
一、题目描述
给你一根长度为 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 = 36
提示：
- 2 <= n <= 58
二、题目解析
我们假设绳子的长度为 10。
先来剪一下，假设一开始剪下来的长度为 1，那么左边绳子的长度为 1，右边绳子的长度为 9，它们的乘积为 1 * 9 = 9。
对于一段一开始长度为 10 的绳子而言，9 是小于 10 的，因此剪下长度为 1 的绳子是无法增大乘积的，更一般的来说，1 和任何数相乘都是那个数本身，因此对于任意长度的绳子来说都不应该剪长度为 1 的绳子下来。
数学证明：n > ( n - 1) * 1。
所以，每次剪绳子的操作都是剪至少长度为 2 的绳子的操作。
当剪下一段长度为 2 的绳子时，剩下的绳子长度为 8。
那么对于长度为 8 的这段绳子来说，它有两个选择，剪或者不剪。
- 不剪，乘积结果为
2 * 8 = 16； - 剪，怎么剪？
对于这两个选择，我们无法第一时间做出决定，因为目前还不知道剪的情况下能否出现大于 16 的结果。
所以，接下来的操作就是去剪第二段绳子。
怎么剪呢？
和剪长度为 10 的那段绳子一样的思路。
剪完之后，第二段绳子也被划分两块区域，a 和 b。
通过剪长度为 10 的绳子与长度为 8 的绳子的操作，我们可以发现：我们在不停的去剪相对的那根 第二段 的绳子，直到剪无可剪为止。
此时我们考虑第二段的情况时，第一段绳子的长度为 2，而事实上，第一段绳子可取的范围为 [ 2，i）。
此时，假设当下绳子的长度为 i。
长度为 n 的绳子剪掉后的最大乘积与求绳子长度为 n - 1 、 n - 2 、 n - 3 的最大乘积求法一样。
假设剪的绳子那段称为 第一段，剪剩下的那段绳子称为 第二段，那么第一段的范围为 [2,i)，第二段可以剪或者不剪，假设 dp[i] 表示长度为 i 的绳子剪成 m 段后的最大乘积，那么，不剪总长度乘积为 j * （ i - j），剪的话长度乘积为 j * dp[ i - j ]，取两者的最大值，即 Max ( j * ( i - j) , j * dp[ i - j] )。
状态转移方程：dp[i] = Max(dp[i], Max(j * (i - j), j * dp[i - j]))
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public int cuttingRope(int n) {
// 长度为 1 的绳子没法剪了
if ( n <= 1 ) return 1;
// 用一个名为 dp 的数组来记录从 0 到 n 长度的绳子剪掉后的最大乘积
// 默认都是 0
int[] dp = new int[n + 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] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
}
2、C++ 代码
class Solution {
public:
int cuttingRope(int n) {
// 长度为 1 的绳子没法剪了
if ( n <= 1 ) return 1;
// 用一个名为 dp 的数组来记录从 0 到 n 长度的绳子剪掉后的最大乘积
// 默认都是 0
vector<int> dp( n + 1 , 0 );
// 由于绳子必须被剪，所以长度为 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] = max(dp[i], max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
};
3、Python 代码
class Solution:
def cuttingRope(self, n: int) -> int:
# 长度为 1 的绳子没法剪了
if n <= 1 : return 1
# 用一个名为 dp 的数组来记录从 0 到 n 长度的绳子剪掉后的最大乘积
# 默认都是 0
dp = [ 0 for _ in range( n + 1 )]
# 由于绳子必须被剪，所以长度为 2 的绳子只有剪成 1 和 1 的两段，乘积结果为 1
dp[2] = 1
# 长度大于等于 3 的绳子才开始进入我们的讨论范围
# 从长度为 3 的绳子开始考虑，讨论它的最大乘积是多少，并不断的延伸绳子的长度
for i in range ( 3 , n + 1 ) :
# 对于长度为 i 的绳子，它可以分为两个区间 j 和 i - j
# j 的范围由 2 开始，因为剪长度为 1 的绳子无法扩大乘积的值
# j 的范围可以延伸至 i - 1
for j in range( 2 , i ) :
# 不剪总长度乘积为 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] = max(dp[i], max(j * (i - j), j * dp[i - j]))
return dp[n]
四、复杂度分析
时间复杂度
时间复杂度为 O(n2) 。
空间复杂度
空间复杂度为 O(n) 。
