数字三角形
f[1][1]=a[1][1];
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++) //状态转移方程如下
f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);最长上升子序列
for(int i=1;i<=n;i++)
f[i]=1; //只有a[i]一个数字
for(int j=1;j<=i;j++){
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
printf("%d\n",ans);最长公共子序列
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);
}
cout<<f[n][m]<<endl;01背包
for(int i=1;i<=n;i++){ //前i个物品
int wi,ci; //每个物品的体积、价值
cin>>wi>>ci;
for(int j=1;j<=w;j++){
if(wi>j){ //体积大于背包容量，放不下，只能不放
f[i][j]=f[i-1][j];
}else{ //体积合适，可选择不放 与 放
f[i][j]=max(f[i-1][j],f[i-1][j-wi]+ci);
}
}
}
cout<<f[n][w]; //n个物品在容量为w的背包中的最大价值完全背包
for(int i=1;i<=n;i++){ //从1到n个物品
for(int j=w[i];j<=m;j++){//从重量w[i]到重量m，能装一直装
if(dp[j]<dp[j-w[i]]+c[i]){//如果原价值<dp[j-w[i]]+c[i]
dp[j]=dp[j-w[i]]+c[i];//更新价值
}
}
}
cout<<"max="<<dp[m]<<endl;多重背包
多重背包转化为01背包问题 把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度是O(V*Σn[i])。
解法一：朴素算法，每种物品多次01背包
#include<iostream>
#include<cmath>
using namespace std;
int n,m,f[6010]; //多重背包
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int vi,wi,si;
cin>>vi>>wi>>si;
for(int k=1;k<=si;k++){ //最多si件
for(int j=m; j>=vi; j--){ //01背包，从后往前
f[j]=max(f[j],f[j-vi]+wi);
}
}
}
cout<<f[m]<<endl;
return 0;
}解法二：二进制优化，转换为01背包 算法的复杂度由O(V*∑n[i])改进到O(V*∑logn[i])，特别注意“拆分物品”的思想和方法，即二进制拆分思想：
比如：整数7,只需要用1 2 4三个数任意组合，就能组合出 0~7 这8种可能。
再比如：整数10，只需要用1 2 4 3（注意最后一个数），就能组合出0~10这11种可能，这样n这个值就被二进制化了。因此如果要讨论10个一样的物品，就转化为讨论4个不同的物品了；而 n 个一样的物品,就转化为log2n个不同的物品进行讨论。
#include<iostream>
using namespace std;
int n,m,v[50001],w[50001],s[50001],f[10001]={0},len=0;
int main(){ //多重背包转01背包问题
cin>>n>>m;
for(int i=1;i<=n;i++){
int vi,wi,si;
cin>>vi>>wi>>si;
if(vi>m) continue; //单个物品价格比m大，直接舍去
if(si>m/vi) si=m/vi; //剪枝，物品价格*数量比m大，留下部分
for(int j=1;j<=si;j=j*2){ //初筛的物品存到v[]、w[]
len++;
v[len]=vi*j; //存入物品进行了二进制拆分
w[len]=wi*j;
si-=j;
}
if(si>0){ //多余的继续存入v[]、w[]
len++;
v[len]=si*vi;
w[len]=si*wi;
}
}
for(int i=1;i<=len;i++){ //01背包问题
for(int j=m;j>=v[i];j--){
if(f[j]<f[j-v[i]]+w[i]) f[j]=f[j-v[i]]+w[i];
}
}
cout<<f[m]<<endl;
return 0;
}分组背包
一般分组背包问题中,每组中只能选择一件物品。这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：
dp[k][v]=max{dp[k-1][v],dp[k-1][v-c[i]]+w[i]} 物品i属于组k
分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题。下面是滚动数组优化后的代码。
#include<iostream>
using namespace std;
int v,n,t,p;
int dp[201]={0},w[40],c[40],a[40][40]={0}; //a[r][c]表示第r组第
int main(){
cin>>v>>n>>t; //容量，物品数量，物品分组数
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i]>>p; //物品的体积，价值，分组
a[p][++a[p][0]]=i; //a[p][0]每组数量，1~a[p][0]该组物品的下标
}
for(int i=1;i<=t;i++){ //枚举1~t组
for(int j=v;j>=0;j--){ //枚举背包容量从v~0
for(int k=1;k<=a[i][0];k++){ //枚举第i组的物品下标1~a[i][0]
if(j>=w[a[i][k]] && dp[j]<dp[j-w[a[i][k]]]+c[a[i][k]]){
//同组中相同容量下，更有价值的胜出
dp[j]=dp[j-w[a[i][k]]]+c[a[i][k]];//更有价值则更新
}
}
}
}
cout<<dp[v]<<endl; //输出容量v的最大价值
return 0;
} 区间DP
//以石子合并为例
for(int i=1;i<=n;i++) //求前缀和
aa[i]=aa[i-1]+a[i];
memset(dp,0x3f,sizeof(dp));//初始化为极大值
for(int i=1;i<=n;i++) dp[i][i]=0;//初始化1个石子合并
for(int len=2;len<=n;len++){ //枚举合并的长度
for(int i=1;i<=n-len+1;i++){ //枚举起点
int j=i+len-1; //i为起点，j为终点
for(int k=i;k<j;k++){ //合并i~k,k+1~j
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+aa[j]-aa[i-1]);
}
}
}
cout<<dp[1][n]<<endl;//最小分数