題目
給你一根長度為n的繩子，請把繩子剪成m段（m鹦聪、n都是整數(shù)账阻，n>1并且m>1），每段繩子的長度記為k[0]泽本，k[1]淘太，...，k[m]规丽。請問k[0]k[1]
...
k[m]可能的最大乘積是多少蒲牧？
例如：當(dāng)繩子的長度為8時，我們把它剪成長度為2赌莺、3冰抢、3的三段，此時最大的乘積是18.
問題解析
- 問題是求最優(yōu)解艘狭；
- 整體的問題的最優(yōu)解是依賴各個子問題的最優(yōu)解挎扰；
- 子問題之間還有互相重疊的更小的子問題翠订；
- 為避免子問題的重復(fù)計算，我們存儲子問題的最優(yōu)解遵倦。從上往下分析問題尽超，從下往上求解問題。
上面的幾個條件可以看出骇吭，屬于動態(tài)規(guī)劃問題橙弱。
動態(tài)規(guī)劃
首先定義函數(shù)f(n)為把長度為n的繩子剪成若干段后各段長度乘積的最大值。
在剪第一刀的時候燥狰，我們有n-1種可能的選擇棘脐，也就是說剪出來的第一段的繩子的可能長度分別為1,2,...,n-1.因此 f(n) = max(f(i)f(n-i))，其中
0<i<n
這是一個從上至下的遞歸公式龙致，由于遞歸會有很多重復(fù)的子問題蛀缝，從而有大量不必要的重復(fù)計算。更好的辦法是按照從下而上的順序計算目代，也就是說我們先得到f(2)屈梁、f(3)榛了，再得到f(4)、f(5)构哺，直到得到f(n)
當(dāng)繩子的長度為2時战坤，只可能剪成長度為1的兩段，因此f(2)=1碟嘴。當(dāng)繩子的長度為3時囊卜，可能把繩子剪成分別為1和2的兩段或者長度都為1的三段，由于 1 x 2 > 1 x 1 x 1袱衷，因此f(3) = 2
C++算法實現(xiàn)
int maxProductAfterCutting_solution(int length) {
if(length < 2) // 長度小于2笑窜，不符合題意
return 0;
if(length == 2) // 長度為2排截，只有一種裁剪方案辐益，剪成兩段各為1智政，所以乘積為1
return 1;
if(length == 3) // 長度為3箱蝠，最大乘積為2
return 2;
// 1 創(chuàng)建數(shù)組并初始化前4個元素
int *products = new int[length + 1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
int max = 0;
// 2 從繩子長度為4開始遍歷
for (int i=4; i<=length; i++) {
max = 0;
for (int j=1; j<=i/2; j++) { // 3 繩子的裁剪方案，計算最大值
int product = products[j]*products[i-j];
if (max<product)
max = product;
products[i] = max; // 記錄對應(yīng)長度的最大值
}
}
// 獲取最大值
max = products[length];
delete[] products;
return max;
}
代碼分析
代碼中牙瓢，子問題的最優(yōu)解存儲在數(shù)組products里矾克。數(shù)組中第i個元素表示把長度為i的繩子剪成若干段之后各段長度乘積的最大值憔足，即f(i)。但是這里需要排除長度小于等于3的情況控妻，否則會產(chǎn)生困惑
當(dāng)length<=3的時候揭绑，我們已經(jīng)直接返回了結(jié)果。另外繩子長度小于等于3時弓叛，一刀都不剪的長度大于剪后的乘積诚纸，這些是特例陈惰，我們需要存儲對應(yīng)的值方便后續(xù)的遍歷計算。從4開始井辆，所有剪后的長度乘積都大于等于不剪的長度溶握。
復(fù)雜度
時間復(fù)雜度為O(n2)，空間復(fù)雜度為O(n)
貪婪算法
- 貪婪算法在對問題求解時萍肆，不從整體最優(yōu)上加以考慮，它所做出的是在某種意義上的局部最優(yōu)解塘揣；
- 選擇的貪貪婪策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)才写，只與當(dāng)前狀態(tài)有關(guān)奖蔓；
策略：當(dāng)n5時锭硼，盡可能多地剪長度為
3的繩子；當(dāng)剩下的繩子長度為4時轰异，把繩子剪成長度為2的繩子暑始。
C++算法實現(xiàn)
int maxProductAfterCutting_solution2(int length) {
if (length < 2)
return 0;
if (length == 2)
return 1;
if (length == 3)
return 2;
// 盡可能多的剪去長度為3的繩子段
int timesOf3 = length / 3;
// 當(dāng)繩子最后剩下的長度為4的時候，不能仔剪去長度為3的繩子段
// 此時更好的方法是把繩子剪成長度為2的兩段牙肝，因為 2 x 2 > 3 x 1
if (length - timesOf3 * 3 == 1)
timesOf3 = 1;
int timesOf2 = (length - timesOf3 * 3) / 2;
return (int)(pow(3, timesOf3))*(int)(pow(2, timesOf2));
}
證明思路
首先嗤朴，當(dāng)n5的時候雹姊，我們可以證明先
2(n-2)>n。也就是說敦姻，當(dāng)繩子剩下的長度大于等于5的時候歧杏，我們就把它剪成長度為3或者2的繩子段。另外旺入，當(dāng)n5時凯力，3(n-3)
2(n-2)急膀，因此我們應(yīng)該盡可能地多剪長度為
3的繩子段龄捡。
前面證明的前提是n5。那么當(dāng)繩子的長度為
4呢晨雳？在長度為4的繩子上剪一刀餐禁，有兩種可能的結(jié)果：剪成長度分別為1和3的兩根繩子突照，或者兩根長度都為2的繩子。很明顯是 2 x 2 > 3 x 1末盔。
復(fù)雜度
時間座慰、空間復(fù)雜度為O(1)
參考
《劍指offer》
