題的描述就不寫(xiě)了。
本篇是《算法導(dǎo)論》中鋼條切割的遞歸實(shí)現(xiàn)（實(shí)際生產(chǎn)中效率很低，復(fù)雜度是指數(shù)增長(zhǎng)的，使用線性規(guī)劃可以將復(fù)雜度由指數(shù)增長(zhǎng)優(yōu)化為線性增長(zhǎng)），以后會(huì)補(bǔ)上線性規(guī)劃實(shí)現(xiàn)茴厉。
分治法適用情景：一個(gè)大問(wèn)題可分割成2份相互獨(dú)立的子問(wèn)題
線性規(guī)劃適用場(chǎng)景：一個(gè)大問(wèn)題分割成的子問(wèn)題需要子子問(wèn)題的結(jié)果
代碼中p數(shù)組是長(zhǎng)度 1-9 對(duì)應(yīng)的價(jià)值，p[0]=0什荣。
遞歸一般都是根據(jù)數(shù)學(xué)歸納法實(shí)現(xiàn)的矾缓。
假設(shè)第i次最優(yōu)解為r(i-1),則第i次的最優(yōu)解可能為r(i-1)+p[1]，也可能是r(i-2)+p[2]稻爬，一般解可以用r(n-i)+p[i]表示嗜闻，需要比較所有解中最大的值。
程序之前先考慮幾個(gè)問(wèn)題：
1桅锄、 怎么覆蓋所有可能的解
2琉雳、 遞歸調(diào)用重復(fù)計(jì)算的位置在哪
3、 怎么知道取到最優(yōu)解時(shí)候的切割方式
public void test(){
int [] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24};
cut(p, 4);
}
public int cut(int[] p, int n){
if (n == 0){
return 0;
}
int q = -1;
for (int i = 1;i <= n;i++){
//max 方法是返回2個(gè)值的最大值
q=max(q, p[i] + cut(p, n - i));
if (i==n){
//當(dāng) i==n 的時(shí)候就會(huì)進(jìn)入上面的if(n == 0)返回 然后通過(guò)max方法獲取最大值
System.out.println("最優(yōu)解： " + q);
}
}
return q;
}
public int max(int a, int b){
return a > b ? a : b;
}
接下來(lái)分析一下程序思路和執(zhí)行順序友瘤。
程序需要如下：（括號(hào)內(nèi)有的是對(duì)前一句話的解釋）
1翠肘、遞歸都要有的出口
2、分析q=max(q, p[i] + cut(p, n - i));
這句是取q和第i個(gè)p對(duì)應(yīng)的價(jià)值加上第n-i的最優(yōu)解（遞歸調(diào)用的）
因?yàn)橛型鈱觙or循環(huán)辫秧，i的值會(huì)從1增加到n（這樣就可以表示所有的解）
執(zhí)行順序：
1束倍、for循環(huán)是什么時(shí)候執(zhí)行的
2、遞歸執(zhí)行的順序
cut(p, 4)
cut(p, 3)
cut(p, 2)
cut(p, 1)
cut(p, 0) //返回cut(p, 0)
cut(p, 0)的順序
1 cut(p, n - i)=0 因?yàn)閚-i==0 然后會(huì)返回 0
2 然后和p[i]相加 后與q求最大值 （最大值是p[i]+0）， 所以 绪妹，q = 1甥桂；
3 獲取完q（最優(yōu)解）之后 ， for循環(huán)執(zhí)行（也就是1的問(wèn)題）
for循環(huán)會(huì)把cut(p, i)的所有情況都會(huì)遞歸（覆蓋n=i時(shí)的所有解）邮旷。
不過(guò)在for循環(huán)的時(shí)候又會(huì)重新遞歸調(diào)用已經(jīng)計(jì)算過(guò)的解黄选。
上面只解釋了最外層的遞歸
cut(p， 0)的結(jié)果返回之后 婶肩，cut(p, 1)會(huì)獲取到這個(gè)返回值 （也就是最外層結(jié)果返回办陷，然后返回到遞歸的上一層， 并給上一層提供結(jié)果狡孔，這樣一直到cut(p, 4)）
怎么理解這個(gè)圖
圖中圓圈中的標(biāo)號(hào)就是對(duì)應(yīng)的cut(p, i)
n=4 i=1 調(diào)用了cut(p, 3) cut(p, 2) cut(p, 1) cut(p, 0) (對(duì)應(yīng)的是4-3-2-1-0 縱向)
n=4 for循環(huán)對(duì)應(yīng)的是 i=3 i=2 i=1 i=0(橫向)
