初级DP
-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)\) 代码
可以线段树求动态区间前缀最大值优化到\(O(nlogn)\)具体请看 初级DP优化（鸽了
变式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.求不经过某个点限制下原问题的答案。
只需给不能经过的点初始化一个负无穷的值即可。
--2.最长上升子序列
设计状态\(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 输出时参考下述代码
点击查看代码
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)\) 代码
---2.乌龟棋
考虑状态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
区间DP状态前两维通常为\(F[i][j]\)表示区间\(i->j\)的某种值
转移通常为枚举一个断点\(k\)来更新\(F[i][j] = F[i][k] ? F[k+1][j] + ?\) 其中\(k\in[i,j)\)
转移时我们要先从小到大枚举一个len再枚举l这样才能保证我们是从小区间转移到大区间的
初始化一般为\(F[i][i]=w[i]or0\)
常见技巧的有环形需要我们开多倍长度断环为链
--1.合并石子
按上述描述我们很容易完成这道题
设状态\(F[i][j]\)表示将区间\([i,j]\)内石子全部合并成一堆的最大得分
枚举断点\(k\)转移\(F[i][j]=max(F[i][j],F[i][k]+F[k+1][j])\)
初始化\(F[i][i]=1\)
最小值只需将转移方程中的\(max\)改为\(min\)即可
时间复杂度\(O(n^3)\) 代码 其实细节还是不少的，不是很好写。
--2.Brackets
一样的设\(F[i][j]\)表示\([i,j]\)最多匹配括号数
转移需要分两种情况 一种是\(F[i][j]=max(F[i][j],F[i][k]+F[k+1][j])\)
当\(s[l]匹配s[r]\)时 \(F[i][j]=max(F[i][j],F[i+1][j-1]+2)\)
时间复杂度\(O(n^3)\)代码
--3.Multiplication Puzzle
注意到左右端点的数不能删除 所以我们设状态\(F[i][j]\)表示\((i,j)\)内的数被删干净的最小代价和
转移\(F[i][j]=min(F[i][j],F[i][k]+F[k][j]+w[k-1]*w[k+1])\)
注意前后都是k因为根据我们的状态意义左右端点是没有被删的
时间复杂度\(O(n^3)\)代码
注意枚举断点k的时候\(k\in(l,r)\)左右都是开区间 理由同上
--4.Palindrome subsequence
设\(F[i][j]\)表示\([i,j]\)内回文子序列的数量
那么得到\(F[i][j]=F[i+1][j]+F[i][j-1]-F[i+1][j-1]\) 根据容斥原理这样可以将新的方案统计进来
还要注意 如果\(s[i]==s[j]\)那么总方案还会多上\(F[i+1][j-1]+1\)即所有原来的回文串左右拼接上和左右两个字符组成一个回文串
时间复杂度\(O(n^2)\)代码
ex:如果是回文子串它是一道什么题呢？