动态规划

背包问题

线性DP

数字三角形

从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
input:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
output:
30

//从下向上DP更新
//f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
for(int j=1;j<=n;j++){
    f[n][j]=a[n][j];//将最后一行输入到f数组中
}
for(int i=n-1;i>=1;i--){//从n-1行开始
    for(int j=1;j<=i;j++){
        f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
    }
}
cout<<f[1][1];

最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
input:
7
3 1 2 1 8 5 6
output:
1 2 5 6
4

vector<int> q;
q.push_back(a[0]);
for(int i=0;i<n;i++){
    if(a[i]>q.back()){
        q.push_back(a[i]);
    }
    else{
        *lower_bound(q.begin(),q.end(),a[i])=a[i];
    }
}
for(auto i:q){
    cout<<i<<" ";
}

cout<<endl<<q.size();

最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
input：
4 5
acbd
abedc
output：
abd
3

//f[i][j]表示A的前i个于B的前j个的最长公共子序列
//f[i][j]=max(f[i-1][j-1]AB都不选,f[i][j-1]A选B不选,f[i-1][j]A不选B选,f[i-1][j-1]+1AB都选)
const int N=1005;
char a[N],b[N];
int f[N][N];
int n=read(),m=read();
scanf("%s,a+1);scanf("%s,b+1);
for(int i=1;i<=n;++i){
    for(int j=1;j<=m;j++){
        f[i][j]=max(f[i-1][j],f[i][j-1]);
        if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
    }
}

区间DP

石子合并

设有 N 堆石子排成一排，其编号为 1，2，3，…N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
input：
4
1 3 5 2
output：
22
假设f[i][j]表示从第i个到第j个合并所付出的最小的代价 f[1][n]即为答案