思路一：動(dòng)態(tài)規(guī)劃

1:首先我們想要求長(zhǎng)度為n的繩子剪掉后的最大乘積，可以從前面比n小的繩子轉(zhuǎn)移而來(lái)

2:用一個(gè)dp數(shù)組記錄從0到n長(zhǎng)度的繩子剪掉后的最大乘積，也就是dp[i]表時(shí)長(zhǎng)度為i的繩子剪成m段后的最大乘積,初始化dp[2]=1

3:我們把繩子剪掉第一段（長(zhǎng)度為j），如果只減去1，對(duì)最后的乘積沒(méi)有任何增益，所以長(zhǎng)度為2開(kāi)始剪

4:剪了第一段后，剩下(i-j)長(zhǎng)度可以不剪。如果不剪對(duì)應(yīng)j*（i-j）;如果剪去對(duì)應(yīng)j*dp[i-j]。取兩者最大值max(j*(i-1)，j * dp[i-j])

5:第一段長(zhǎng)度j可以取的區(qū)間為[2),對(duì)所有j不同的情況取最大值，因此最終dp[i]的轉(zhuǎn)移方程為dp[i] = max(dp[i],j*max(dp[i-j],(i-j)))

class Solution { public:int cuttingRope(int n) {if(n<2) return 0;vector<int> dp(n+1);//當(dāng)繩子長(zhǎng)度為i時(shí)候可能的最大乘積為dp[i]//確定初始化條件dp[2]=1; //0跟1減沒(méi)有意義for(int i=3;i<=n;i++){for(int j=2;j<i;j++){ //j表示剪下來(lái)的繩子大小，當(dāng)剪下1時(shí)候沒(méi)意義，所以從2開(kāi)始//繩子有兩種方式，一種是剪下之后，剩下的再剪下最大為j*dp[i-j]//一種是剪下之后，剩下的不減了，剩的為j*(i-j);dp[i] = max(dp[i],j*max(dp[i-j],(i-j))); //里面一直跟之前的遍歷減過(guò)的結(jié)果比較 }}return dp[n];} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode-剑指 Offer 14- I. 剪绳子的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。