给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
输入一个数n,意义见题面。(2 <= n <= 60)
输出答案。
示例1
8
18
解法一:
使用动态规划解决 动态规划,先自上而下分析,在长度为n的绳子所求为f(n),剪下一刀后剩下的两段长度是i和n-i,在这个上面还可能继续减(子问题),所以: f(n)=max(f(i)×f(n−i))
然后自下而上的解决问题,可以从f(1)开始向上计算并打表保存,最终获得f(n)的值。 1、C++
class Solution {
public:
int cutRope(int number) {
if(number < 2)//因为要求长度n>1,所以这里返回0表示输入非法
return 0;
if(number == 2)//长度为2时,因为要求剪下段数m>1,所以最大是1x1=1
return 1;
if(number == 3)//长度为3时,因为要求剪下段数m>1,所以