1.数字三角形模型
1.多为从在满足某些限制的条件下一个点移动到另有一个点
我们可以通过对最后一个状态的前一个状态来把转移方程求出来
注意在求最小值的时候要从开头的方向转移过来所以第一行和第一列会出问题我们要先初始化为负数
2.来回走的话我们可以理解为两个人同时移动,满足移动步数
转移方程较为简单
如果说是右下右下的移动,同时数据范围是20或者40我们考虑dfs(折半dfs)
2.最长上升子序列
1. 多为需要满足某种单调上升的或者下降的关系
2.最普通的有n^2的操作
3.nlogn的贪心优化
4.状态较少的状态机dp优化
3.背包问题
简单的背包问题有01,或者是完全背包一定是要牢记的,同时注意如果是二维的就可以保存每一维度存储的信息,我们考虑到如果上一维度需要加一些东西来影响下一维度就可以考虑加一个状态栏,组成01背包
同时如果是可以推理出要求一段连续的选择可以直接对线段就行处理,对线段进行背包