dp常用方法

1.常用的填表法和刷表法：

填表法就是利用状态转移方程和上一个状态来推导出现在的状态（相当于知道已知条件，将答案填入）

刷表法就是利用当前的状态，把有关联的下一状态都推出来。

2.取最大值和统计答案区别：最大值的题目，不允许有空缺为0的情况，必须一步一步的转移，不能跳步；

而统计答案的题目，可以只由有答案的状态跳到下一合法状态，不合法状态可以为0。

3.滚动数组两种方法：

一种是直接覆盖，如背包的优化；第二种是需要与上一行进行无序比较，有可能要比较到所有状态，所以定义两行的数组，用i%2来换行。

4.最优子结构与无后效性：

最优子结构即子问题的最优解一定能推出来当前问题的最优解；

无后效性即当前状态已经确定，则以后的状态与之前的状态无关。

典型的例子： 1）.传纸条类型的题，如果上下左右都能走，就会具有后效性。

2）.P1437.如果按正常顺序从上往下搜，就会发现有之前的状态重复计算的情况，因此要从右往左搜。

5.常用避免不合法状态转移的方法：如果是取最大值，就设数组为负无穷，将初始状态初始化为0.这样当碰到不合法的状态时，这届计算出负无穷，达到舍去的目的。

6.常用推转移方程的方法：

~~0).思考问题是否满足无后效性和最优子结构，没有还做个p~~

1).思考出当前所有的状态f[i][j][k][...]（f[i][j][0], f[i][j][1] 或只有 f[i][j][k]）

2).根据题意列出每种状态所有的决策(跳转机制)，即各种取max操作或连加连乘。 (f[i][j][k] -> max(...), +=..., * =...)

3).将下一状态通过决策枚举出来(f[i+1][j][k], f[i+1][j+1][k], f[i+1][v][k-j],v>=j-1)

以上就可以做题了，但用的是刷表法。

(重点) 4).将下一状态与当前状态通过决策建立联系，并将i+1,j-1,k+v等下一状态的系数迭代为i,j,k,以将下一状态当作当前状态，将当前状态转化为上一状态，用填表法做题。(f[i+1][j][k]->f[i][j][k],f[i+1][j+1][k]->f[i][j][k] 可以变为 f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][k]))

5) 常见跳转与状态设置

1.设考虑到第\(i\)个时的\(f[i]\),下一次跳转到\(f[i+1]\)，如传统背包 2.设考虑到前\(i\)个时的\(f[i]\),跳转可能是将第\(i+1\)个插入到前\(i\)个里，也可能直接跳转到\(j(j>i)\)，忽略\([i+1,j-1]\)的物品。