15.1 钢条切割

动态规划(dynamic programming)与分治方法相似，都是通过组合子问题的解来求解原问题。
DP算法对每个子问题只求解一次，将其解保存在一个表格中，避免重复计算。

DP设计

1.确定状态
2.构建状态转移方程
3.初始化及处理边界问题
4.确立规划顺序

经典名句

时空权衡(Time-Memory trade-off)
朴素递归算法之所以效率很低，是因为它反复求解相同的子问题，因此，动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来，如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。

动态规划顺序

top-down with memoization

按照自然递归形式过程，但过程中保存每个子问题的解，当需要一个子问题的解时，首先检查该子问题是否已解，若已解，直接获取结果，否则进行计算。

bottom-up method

一般需要恰当定义子问题的“规模”，使得任何子问题的求解都只依赖于“更小的”子问题的求解，因而我们可以将子问题按规模顺序，由小到大的顺序进行求解。

code

recursive

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

using namespace std;

// 15.1 切钢条问题
// 递归法求解: 时间复杂度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): 前长度为i的小棒不变，后n-i继续切断
        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;

// 切钢条
// 带备忘的自顶向下 动态规划
// 时间复杂度： O(n)
int memoized_cut_rod(int p[],int n,int visit[]){
    // 检查标记
    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;

// 切钢条
// 动态规划：自底向上
// 时间复杂度： O(n)
int main(){
    int p[]={0,1,5,8,9,10,17,17,20,24,30};
    int n=4;
    // dp[i]: 钢条长度为i时，切割最大收益
    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;

// 切钢条
// 自底向上动态规划
// 记录切割后，每段长度
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;
}