-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.求不经过某个点限制下原问题的答案。
只需给不能经过的点初始化一个负无穷的值即可。
--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 输出时参考下述代码
点击查看代码
/*
ÒÔP½áβ·½°¸
int z[], cnt;
do
{
z[++ cnt] = p;
p = pre[p];
} while(p != 0);
reverse(z + 1, z + 1 + cnt);
*/