15.1 鋼條切割

動(dòng)態(tài)規(guī)劃(dynamic programming)與分治方法相似，都是通過組合子問題的解來求解原問題。
DP算法對(duì)每個(gè)子問題只求解一次，將其解保存在一個(gè)表格中，避免重復(fù)計(jì)算。

DP設(shè)計(jì)

1.確定狀態(tài)
2.構(gòu)建狀態(tài)轉(zhuǎn)移方程
3.初始化及處理邊界問題
4.確立規(guī)劃順序

經(jīng)典名句

時(shí)空權(quán)衡(Time-Memory trade-off)
樸素遞歸算法之所以效率很低，是因?yàn)樗磸?fù)求解相同的子問題，因此，動(dòng)態(tài)規(guī)劃方法仔細(xì)安排求解順序，對(duì)每個(gè)子問題只求解一次，并將結(jié)果保存下來，如果隨后再次需要此子問題的解，只需查找保存的結(jié)果，而不必重新計(jì)算。

動(dòng)態(tài)規(guī)劃順序

top-down with memoization

按照自然遞歸形式過程，但過程中保存每個(gè)子問題的解，當(dāng)需要一個(gè)子問題的解時(shí)，首先檢查該子問題是否已解，若已解，直接獲取結(jié)果，否則進(jìn)行計(jì)算。

bottom-up method

一般需要恰當(dāng)定義子問題的“規(guī)?！保沟萌魏巫訂栴}的求解都只依賴于“更小的”子問題的求解，因而我們可以將子問題按規(guī)模順序，由小到大的順序進(jìn)行求解。

code

recursive

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

// 15.1 切鋼條問題
// 遞歸法求解: 時(shí)間復(fù)雜度T(n)=2^n
int cut_rod(int p[],int n){
    if(n==0) return 0;
    int q=-1;
    for(int i=1;i<=n;i++){
        // q:不切斷
        // p[i]+cur_rod(p,n-1): 前長(zhǎng)度為i的小棒不變，后n-i繼續(xù)切斷
        q=max(q, p[i]+cut_rod(p,n-i));
    }
    return q;
}

int main(){
    int p[]={0,1,5,8,9,10,17,17,20,24,30};
    int n=4;
    int res=cut_rod(p,n);
    cout << res << endl;
    return 0;
}

top-down

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

// 切鋼條
// 帶備忘的自頂向下 動(dòng)態(tài)規(guī)劃
// 時(shí)間復(fù)雜度： O(n)
int memoized_cut_rod(int p[],int n,int visit[]){
    // 檢查標(biāo)記
    if(visit[n]>=0) return visit[n];
    if(n==0) return 0;
    int q=-1;
    for(int i=1;i<=n;i++){
        q=max(q, p[i]+memoized_cut_rod(p,n-i, visit));
    }
    visit[n]=q;
    return q;
}

int main(){
    int p[]={0,1,5,8,9,10,17,17,20,24,30};
    int n=4;
    int visit[n+1];
    for(int i=0;i<n+1;i++){
        visit[i]=-1;
    }
    int res=memoized_cut_rod(p,n,visit);
    cout << res << endl;
    return 0;
}

bottom-up

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

// 切鋼條
// 動(dòng)態(tài)規(guī)劃：自底向上
// 時(shí)間復(fù)雜度： O(n)
int main(){
    int p[]={0,1,5,8,9,10,17,17,20,24,30};
    int n=4;
    // dp[i]: 鋼條長(zhǎng)度為i時(shí)，切割最大收益
    int dp[n+1];
    // 初始化
    dp[0]=0;
    for(int i=1;i<=n;i++){
        int q=-1;
        for(int j=1;j<=i;j++){
            q=max(q,p[j]+dp[i-j]);
        }
        dp[i]=q;
    }
    cout << dp[n] << endl;
    return 0;
}

extended bottom-up

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

// 切鋼條
// 自底向上動(dòng)態(tài)規(guī)劃
// 記錄切割后，每段長(zhǎng)度
int main(){
    int p[]={0,1,5,8,9,10,17,17,20,24,30};
    int n=4;
    int dp[n+1];
    int res[n+1];
    dp[0]=0;
    int q;
    for(int i=1;i<=n;i++){
        q=-1;
        for(int j=1;j<=i;j++){
            if(q<p[j]+dp[i-j]){
                q=p[j]+dp[i-j];
                res[i]=j;
            }
        }
        dp[i]=q;
    }
    cout << dp[n] << endl;
    while(n>0){
        cout << res[n] << " ";
        n=n-res[n];
    }
    cout << endl;
    return 0;
}