前序
動態(tài)規(guī)劃與貪婪算法
如果面試題是求一個問題的最優(yōu)解（通常是最大值和最小值）菱属，而且該問題可以分解為若干個子問題违诗，并且子問題之間還有重疊的更小的子問題，就可以考慮用動態(tài)規(guī)劃來解決這個問題分瘾。
動態(tài)規(guī)劃問題的第一個特點：求問題的最優(yōu)解
第二個特點：整體問題的最優(yōu)解依賴于子問題的最優(yōu)解该互。
第三個特點：大問題可以分解為若干個小問題，小問題之間還有相互重疊的更小的子問題辕宏。
第四個特點：從上往下分析問題畜晰，從下往上求解問題
貪婪算法和動態(tài)規(guī)劃不同，應(yīng)用貪婪算法解決問題時瑞筐，每一步都可以做出一個貪婪的選擇凄鼻，基于這個選擇我們確定能夠得到最優(yōu)解。
題目
給你一根長度為n的繩子聚假，把繩子剪成m段（m块蚌、n都是整數(shù)且m > 1, n > 1）,m段繩子的長度依然是整數(shù)，求m段繩子的長度乘積最大為多少膘格？
- 比如繩子長度為8匈子，我們可以分成2段、3段闯袒、4段...8段，只有分成3段且長度分別是2游岳、3政敢、3時能得到最大乘積18
動態(tài)規(guī)劃的方式去解決，一共有n-1個分割方式去分割整體問題以及每一個子問題胚迫，設(shè)置一個長度為length+1的數(shù)組喷户，記錄各個分別為4到總長度為length的最大值，如果是長度2,3以及小于1访锻，直接返回其唯一的選擇乘積為1,2以及0褪尝。如果為4，則開始找最大乘積期犬，記錄在product中河哑，product初始設(shè)置為各自的下標(biāo)值，0龟虎，1璃谨，2，3。雙重循環(huán)佳吞，第一層表示f(n)=max(f(i)×f(n-i))中的n（4-length）拱雏，第二層是小于n的一半的數(shù)，也就是函數(shù)中的i底扳，（1-n/2）
所以雙重循環(huán)保證找出不同對的組合铸抑，每次取之前找到的相應(yīng)位置的最大值，最后輸出最后一位衷模。
代碼如下：
//時間復(fù)雜度為O(n2),空間復(fù)雜度為o(n)
public static int maxProductAfterCutting(int length) {
if (length<2){
return 0;
}
if (length==2){
return 1;
}
if (length==3){
return 2;
}
/**
* 多加一個長度鹊汛，因為起始是從1開始
* 123位置上直接設(shè)置長度，4以后選用區(qū)域最大值算芯，保證最大值是唯一的
*/
int[] products = new int[length+1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
for (int i=4;i<=length;i++){
int max = 0;
//一半有效
for (int j=1;j<=i/2;j++){
//得到max{f(i)*f(n-i)}
int product = products[j]*products[i-j];
if (product > max){
max = product;
}
}
//保存f(n)最大值
products[i] = max;
}
return products[length];
}
貪婪法
/**
* 時間和空間復(fù)雜度都為o(1)
* 數(shù)學(xué)證明：
* 1柒昏、當(dāng)n<5時，我們會發(fā)現(xiàn)熙揍，無論怎么剪切职祷，乘積product <= n，n為4時届囚，product最大為2*2=4有梆；
* 2、當(dāng)n>=5時意系，可以證明2(n-2)>n并且3(n-3)>n泥耀。而且3(n-3)>=2(n-2)。所以我們應(yīng)該盡可能地多剪長度為3的繩子段蛔添。
* 化成盡可能多的長度為3的段痰催，其中如果最后余1，則留下一個3提供給1迎瞧，組成4夸溶，最后計算乘積
* @param length
* @return
*/
public static int maxProductAfterCutting2(int length) {
if (length<2){
return 0;
}
if (length==2){
return 1;
}
if (length==3){
return 2;
}
//盡可能的找到可以分為多少個長度為3的段
int countof3 = length/3;
if (length%3 == 1){
countof3--;
}
int countof2 = (length-countof3*3)/2;
return (int)Math.pow(3,countof3)*(int)Math.pow(2,countof2);
}
public static void main(String[] args) {
System.out.println(maxProductAfterCutting(8));
System.out.println(maxProductAfterCutting2(8));
}
