- 背包问题
- 01背包问题
- 完全背包
- 多重背包问题 I
- 多重背包问题 II
- 分组背包
- 线性DP
- 最长上升子序列
- 最长上升子序列 II
- 最长公共子序列
- 最短编辑距离
- 编辑距离
- 区间DP
- 石子合并
状态表示 : f [ i ] [ j ] f[i][j] f[i][j] 前 i i i个物品中,体积为 j j j的最大价值
状态转移 : f [ i ] [ j ] = f [ i − 1 ] [ j ] ( j − v < 0 ) f[i][j] =f[i-1][j](j-v>w[i]>>s[i]; for(int i=1;i=0;j--) { for(int k=1;km; for(int i = 1;i>v>>w>>s; for(int k = 1;k= k*v;j--) f[j] = max(f[j],f[j-k*v]+k*w); s-=k; } if(s) { for(int j = m ;j>=s*v;j--) { f[j] = max(f[j],f[j-s*v]+s*w); } } } coutm; for(int i=0;i>s[i]; for(int j=0;j>v[i][j]>>w[i][j]; } } for(int i=0;i=0;j--){ for(int k=0;k=1;k--)也可以 if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); } } } cout
