背包:
01:
for(int i=1;i<=n;i++)
for(int j=V;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
完全背包:
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
多重背包 及优化
分组背包 同 01背包
线性dp: 数字三角形
最长上升子序列
最长上升子序列2优化(二分查找,较难理解)
最短编辑距离(状态转移过程,较难理解)
区间dp 固定模板:
for(len=2;len<=n;len++)
{
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++)
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+C);
}
}
计数类dp: 整数划分 没看
数位统计dp: 好难
状态压缩dp: 好难
树形dp: 没看
记忆化搜索: 滑雪 没看
这是字符串