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;
}
