剑指 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) 。