-0. DP的概念与设计和实现
概念：DP从本质上讲是图论问题的中的一种，DP的每一种状态所对应的便是一张图上的点，转移对应的便是图上的边。
如果是求最值，那便是图论中的最短路或最长路；如果要求方案数，那便是图论中的路径统计问题。
设计：DP的设计有三大要素：状态，转移方程，初始化。
实现：DP的实现通常是三种方式，从当前状态向可能状态转移，从可能前继状态向当前状态转移，记忆化搜索。通常根据实现的难易来选择。
-1. 入门DP
--1.数字三角形是一个很好的例子
我们先确定状态 \(F[i][j]\)表示到达当前位置\((i,j)\)所累积的最大的数是多少。
接下来考虑转移\(F[i][j]=max(f[i-1][j],f[i-1][j-1])+w[i][j]\).
不需初始化。
时间复杂度\(O(n^2)\) 代码
变式1.求在模100后的最大值。
当DP条件变多时，我们便考虑给DP多开一维来记录状态\(F[i][j][k]\)表示当到达位置\((i,j)\)时模\(100\)等于\(k\)是否可能\(1\)表示可能\(0\)表示不可能。
于是我们得到转移方程\(F[i][j][k]->F[i+1][j][(k+w[i+1][j])\%100]andF[i+1][j+1][(k+w[i+1][j+1])\%100]=1\)
最后扫描最后一行每一个位置\(1-k\)是否合法即可。
时间复杂度\(O(n^3)\)。
变式2.求必经某个点限制下原问题的答案。
只需先算\((1,1)\)到该点的最大值再算该点到最后一排的最大值即可。
变式3.求不经过某个点限制下原问题的答案。
只需给不能经过的点初始化一个负无穷的值即可。
设计状态\(F[i]\)表示以i位置结尾的最长子序列长度
得到转移\((a_j>a_i)\)时\(F[i]=max_{j\in[1,i)]}(F[i],F[j]+1)\)
初始化F[i]=1
时间复杂度\(O(n^2)\) 代码
考虑记录方案数
新开一个g数组
点击查看代码
if(f[j] + 1 > f[i]) { f[i] = f[j] + 1; g[i] = 0; pre[i] = j;}
if(f[j] + 1 == f[i]) g[i] += g[j];
如果第一行执行那么第二行也必然执行 这样写才能达到我们想要的效果
考虑记录一种方案
如上方代码中记录的前继数组pre 输出时参考下述代码
点击查看代码
/*
ÒÔP½áβ·½°¸
int z[], cnt;
do
{
z[++ cnt] = p;
p = pre[p];
} while(p != 0);
reverse(z + 1, z + 1 + cnt);
*/
一些例题
---1.滑雪
考虑\(F[i][j]\)表示到位置\((i,j)\)最多滑雪步数
转移即为上下左右四个方向取\(max\)向当前位置转移并\(+1\)
初始化所有点为\(1\)
这样对吗？ NO。 因为我们的转移需要从步数少的地方向步数多的地方转移（这类似我们要先以高度进行一个拓扑排序）然后再判断当前位置上下左右哪个位置高度大于该处才能转移到该处
时间复杂度为check ans的\(O(nm)\) 代码
考虑状态F[x][a][b][c][d]$为当前在x位置使用了a张1牌b张2牌...
显然x可以通过1+a+2b+3c+4d得到 于是便可以压掉
转移便是当前位置使用1或2或3或4向后转移即可
时间复杂度\(O(max种类牌数^4)\) 代码
下面介绍几种比较套路的DP
-2.区间DP