劍指offer–剪繩子

文章目錄

• 劍指offer--剪繩子
• • 一、題目描述
  • 二、分析
  • 三、代碼

一、題目描述

二、分析

既然這道題考的是貪心，我們就用貪心來解決，不用其他的方法；

動態規劃求解問題的四個特征：
①求一個問題的最優解；
②整體的問題的最優解是依賴于各個子問題的最優解；
③小問題之間還有相互重疊的更小的子問題；
④從上往下分析問題，從下往上求解問題；

• 對于這道題，我們先確定最多可以分得的段數，對于長度為n的繩子（n > 1），如何把它分為整數長的m段（m > 1），
• 對于m，我們最大可以分多少段？---->n段，剛好每段的長度都是1，但是這樣最后分得的結果乘積為1，肯定不是最大的。
• 所以m的最大值為繩長n的一半，因為一旦超過繩長的一半，就肯定至少有一段的長度為1，達不到結果乘積最大的目的
• 現在長度為n的繩子最多可以分得的段數已經確定，但是我們怎么確定分為那幾個段可以使結果的乘積最大呢？
• 這里就需要才用動態規劃的自下而上的求解問題的方式，在這里也算是一種枚舉吧，具體點做法是：
• 對于長度為n的繩子，我們先求出長度為1，2，3，4，....，n - 2，n - 1的繩子分為m段的最大乘積結果，那么長度為n的繩子在分為m段的最大乘積結果就肯定是分為1，2，3，4，....，n - 2，n - 1中的某一部分而已
• 那么長度為1，2，3，4，....，n - 2，n - 1怎么求其分為m段的最大乘積呢？這不就滿足動態規劃的問題了嗎？--整體的問題的最優解是依賴于各個子問題的最優解
• 顯然base case就是在繩長為2時和3時的情況
• 但是當繩長為2和3也分兩種情況：
• 1.繩長n大于3時，子問題：繩長為2 或者3就可以不用分段，這樣可以使分段結果乘積更大。
• 2.繩長n小于等于3時，自問題：繩長為2時，最大的結果為1，因為m是大于1 的，就是必須分段，同理當繩長為3時，最大的分段結果為2

三、代碼

class Solution { public:int cutRope(int number) {//記錄求長度為number前的子長度結果vector<int> dp(number + 1);// number<=3的情況，因為m>1必須要分段，例如：3必須分成1、2；1、1、1 ，//number=3最大分段乘積是2,if(number == 2)return 1;if(number == 3)return 2;//下面是number>=4的情況，跟number<=3不同，4可以分很多段，比如分成1、3，//這里的3可以不需要再分了，因為3分段最大才2，不分就是3。記錄最大的。dp[0] = 0;dp[1] = 1;dp[2] = 2;dp[3] = 3;//保存結果int ret = INT_MIN;//主要思想是每次把繩子分為j份，每次分別求最大的乘積//再在過程中記錄最大值for (int i = 4; i <= number; i++) {for (int j = 1; j <= i/2 ; j++) {//更新最大值，這里你只看到分為兩端，一段j，另一端為i - j//但是j和i - j在之前的計算中同樣經歷了這樣的計算判斷//即j和i - j是分為m段中最大最優的結果//所以i同樣就是分為m段中最大最優的結果ret = max(ret,dp[j] * dp[i - j]);}dp[i] = ret;}return dp[number];} };

總結

以上是生活随笔為你收集整理的剑指offer--剪绳子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。