动态规划,着重复盘
给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1,m<=n),每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
动态规划,从长度4开始,因为123都是一眼就能看出的,第一层遍历更新每个长度的最大值,第二层遍历,列举所有分成两段的情况,更新最大值
```c++
class Solution { public: int cutRope(int number) { if(number < 2) return 0; if(number == 2) return 1; if(number == 3) return 2;
vector<int> dp(number+1, 0);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for(int i=4; i<=number; i++){
//int maxValue = 0;
for(int j=1; j<=i/2; j++){
int temp = dp[j] * dp[i-j];
dp[i] = max(dp[i], temp);
}
}
return dp[number];
}
};