背包问题:
01背包:前i个物品体积为j的价值,这个物品是要还是不要
完全背包:f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i])
多重背包:0,1,2,3....
分组背包:三重循环
线性dp:
最长上升子序列:一维以i结尾的最长上升子序列的长度 相当于两层循环
最长公共子序列:四种情况 00 01 10 11
最短编辑距离:也是看最后一个的关系来判断的状态转移方程的
区间DP:
石子合并的问题在区间循环时要从2开始循环,因为这里取得是最小值,f[l][l]在计算的时候会被记成是无穷大的,如果从1开始循环,要在赋值之前进行特判
树型DP:
数位DP:
插头DP:
环形DP: