dp 教程

接触 dp

dp 是什么

在算法竞赛中，动态规划是一种解决问题的思想，这种思想着眼于把复杂问题分解为容易解决的子问题，最后通过对子问题答案的合并进而得到复杂问题的答案。

在实际应用中，动态规划常常与计数等有着简单递推式的问题混为一谈，不过，尽管那些朴素递推离着dp很远，但是却仍可以为初学者提供一定的借鉴。
​

朴素递归

接下来我们通过研究一些简单的朴素递推问题来初步接触dp。
​

楼梯问题（luogu U531202）¹

不难发现，在任何时候，若我们处于$3\le k\le n$层台阶，则我们上一步一定位于$k-1$或$k-2$层台阶，也就是说，若$f_k$表示到达第$k$层的方案数，则直接影响$f_k$的只有$f_{k-1}$与$f_{k-2}$。直接来说，

$f_{k}=f_{k-1}+f_{k-2}\ \ (3\le k \le n)$  

而$k=1$和$k=2$的情况可以直接给出
​

$f_1=f_2=1$

根据上面两个式子，我们就能写出核心代码：
​

for(int i=3; i<=n; i++){
	f[i] = f[i-1] + f[i-2];
}
​

但值得注意的是，当n较大时，$f_n\approx 2f_{n-1}$，也就是说$f_n$是以指数级增长的，如果不加处理，$int$类型很快就会溢出。

面对这种情况，如果题目没有给出明确说明，则我们需要将$int$拓展到$long\ long$；如果如此题一样已经给出要求，在模的运算规则的保证下，我们只需要在$for$循环的过程中取模就可以保证最终结果的正确，以下是修改后代码：
​

int mod = 1e9 + 7;
for(int i=3; i<=n; i++){
	f[i] = (f[i-1] + f[i-2])%mod;
}
​

最小路径和（LeetCode .64）²

这个问题与上文有着相似的结构，即当我们处于$[x,y](2\le x \le n-1 ,2\le y \le m-1)$时，我们的上一步一定为$[x-1,y]$或$[x,y-1]$。若我们设$f_{x,y}$为从$[1,1]$到达$[x,y]$所能得到的最小路径和，那么直接影响$f_{x,y}$的仅为$f_{x-1,y}$和$f_{x,y-1}$，于是我们可以得到递推方程：
​

$f_{x,y}=min(f_{x-1,y},f_{x,y-1})+grid[x][y],(2\le x\le n,2\le y\le m)$

而对于左边界和上边界，它们只能从上方或者左方走过来，因此我们也能得到它们的递推方程：
​

$f_{x,1}=f_{x-1,1}+grid[x][1]$

$f_{1,y}=f_{1,y-1}+grid[1][y]$

此时，我们便可以写出核心代码：
​

for(int i=1;i<=n;i++){
	f[i][1]=f[i-1][1]+grid[i][1];
}
for(int j=1;i<=m;j++){
	f[1][j]=f[1][j-1]+grid[1][j];
}
for(int i=2;i<=n;i++){
	for(int j=2;j<=m;j++){
		f[i][j]=min(f[i-1][j],f[i][j-1])+grid[i][j];
	}
}
​

不难发现，这两道**朴素递推**，题目本身就具有相当的清晰性，寻找递推式也并不麻烦，以至于新手学dp时，看过两三个讲解这种朴素递推的视频就认为自己掌握了dp的技巧，但真正做起题目，却发现无论如何也找不到所谓的递推式，甚至看不出这是一个动态规划题。

“通过一两个例子就能掌握dp”，这种错误观念是绝对要被纠正的，事实上，普通人就算经过再多练习也很难完全掌握dp，原因是dp作为一种解决复杂问题的思想，本身并不是明确而清晰无疑的，死记硬背板子的方式是行不通的。只有通过长久的做题，积累起来的题感才是解决dp问题的法宝，但这一切都建立在对于dp的深刻认识之上，因此，本文正篇将着眼于**dp的一些重要概念**，**几种经典dp的介绍**以及**一个用于系统化理解部分dp的方法。**
​

认识 dp

状态

在一道给定的题目中，经常会有这样那样的参数来约束，用上面的题目最小路径和来举例子，约束条件就是坐标x,y。于是我们说，状态就是在若干个约束条件下满足题目条件的符号，更具体来说，我们把约束条件看作自变量，那么状态就是关于这些变量的多元函数， f(x,y......）。

那些由题目条件可以直接得到的状态我们称为初状态，最终答案所在的状态就是末状态，其余状态就是中间状态。

因此dp题目我们可以看作由初状态到达末状态的过程，其间我们需要经历一系列中间状态。
​

状态转移

从一个状态到另一个状态的过程，我们称之为转移。

这些转移往往要满足一系列条件。这些条件我们可以用一系列方程来描述，这些方程我们称之为状态转移方程，其结构与上面例题中我们分析得到的递推式类似。
​

无后效性

而状态转移方程还需要满足无后效性，即我为了状态的转移而做出的行为不能影响更远几步的状态。

或者说，能够影响的步数应该是在状态转移方程中写定了的，对于任何特征的数据都应该满足。
​

从 dfs 到 dp

如果你记忆不错的话，你应该记得对于爬楼梯这道题我们曾经用dfs的方法做过，而当时，面对数据过大时的TLE时，我们被突然告知一种用递推式的解法，当时你可能只是模模糊糊地接受了有这样的概念，却没有深入思考dfs如何与递推产生联系。

下面我要说的是，对于一部分，特别是经典的dp问题，我们都可以通过dfs式的递归思考方式来渐进地得到dp。

之所以要分享这种方法，是因为递归天然的就把复杂问题分解为简单的子问题思考，这更符合我们的日常经验和思维方式，因此通过dfs来得到dp是有意义的。
​

Frog 1（atcoder Edu dp A）³

很明显，这是走楼梯问题的变形，具体来说，是加权后的楼梯问题。
​

DFS

用递归的思想来思考这个问题是很容易的，我们先来考虑如下问题：如果让我们在$n-1$层或$n-2$层选择一层，并一步走到第$n$层，我们该如何选择可以得到最优的答案？

若我们设$f_i$为从$1$到$i$能得到的代价最小累加和，那么不难看出，这个问题的答案应该是：
​

$f_n=min(f_{n-1}+|h_n-h_{n-1}|,f_{n-2}+|h_n-h_{n-2}|)$

这里$h_{n}$，$h_{n-1}$和$h_{n-2}$都是已知的，于是我们只需要找到使得答案最优的$f_{n-1}$和$f_{n-2}$就可以，那么我们如何找到这样的$f_{n-1}$和$f_{n-2}$呢？

假设$f_{n-1}$可以有两个取值$a$和$b$，其中$a \le b$，贪心地思考，$f_{n-1}$取$a$至少不会是更劣的。

也就是说，我们要找到更小的$f_{n-1}$。

注意到，这就是原问题规模缩小后的问题，因此求解$f_{n-1}$的过程与$f_{n}$是一样的。它具有天然的递归特征，而上面给出的公式就是递归关系式，接下来我们只要再找到递归边界就可以写出代码。

实际上，递归边界很好找：
​

$f_1=0,f_2=|h_2-h_1|$

于是我们可以得到核心代码：
​

int dfs(int i){
	//递归边界
    if(i==1)return 0;
    if(i==2)return abs(h[2]-h[1]);

	//下发子问题
    int res=min(dfs(i-1)+abs(h[i]-h[i-1]),dfs(i-2)+abs(h[i]-h[i-2]));
    return res;
}
​

记忆化搜索

我们不妨将$dfs(x)$看作一个父节点，它每次把任务传递给子节点$dfs(x-1)$和$dfs(x-2)$，并最终在回溯时得到答案。

这种结构实际上是一棵树，直接点说，是二叉树，这里我们以$n=5$时为例，画出$dfs$的树图：
​

​​

我们在dfs时，实际上就是遍历了这样一颗树，用这样的树图可以把递归的结构更清晰的给出。

同时，我们在使用dfs时的问题也更加明显：
​

​​

如图所示，绿色是第一次遇到该节点，红色则是第二次甚至更多次遇到该节点。这说明一个节点可能被不止计算了一次，特别是紫框标出的部分，以3为根节点的整颗子树都被重新计算了，在$n$较小时，多余计算带来的负荷的影响不算明显，但是若$n$继续增大，重复计算会显著提高程序的运行时间，因此，我们需要一种办法来储存每个节点的计算结果，让其只计算一次，在后续，该节点被调用时，我们直接返回储存的值，来减少运算。

这种方法我们称之为记忆化搜索。

很明显，我们可以用一个一维数组来完成这个事情，因为每个节点只有一个信息来代表它。于是我们可以用$cache[i]$来表示$dfs(i)$所得到的最终答案，并把$cache[i]$初始化成$-1$表示该节点没有被计算过。

具体代码如下：
​

const int nmax = 200000;
int h[nmax+10],cache[nmax+10];
int dfs(int i){
    if(cache[i]==-1)
        cache[i]=min(dfs(i-1)+abs(h[i]-h[i-1]),dfs(i-2)+abs(h[i]-h[i-2]));

    return cache[i];
}
void solve(){
    int n;
    cin>>n;
    //初始化
    for(int i=1;i<=n;i++)cache[i]=-1;
    for(int i=1;i<=n;i++)cin>>h[i];

    cache[1]=0,cache[2]=abs(h[2]-h[1]);
    return void(cout<<dfs(n));
}
​

我们用如下方式来检验记忆化搜索对dfs的优化程度：每次进入dfs时都让$tot++$，并在最后输出$tot$的值，当n=20时：

$dfs:$​$tot=13529$  

记忆化搜索：$tot=37$  

记忆化搜索把接近指数级别的时间复杂度优化到了线性时间复杂度，卓有成效。
​

DP

如果你在上面对$dfs$和记忆化搜索的讲解中进行了足够的思考，那么现在从记忆化搜索到$dp$的路径已经呼之欲出。为了写出一道$dp$题目，我们总是需要找到一个无后效性的状态转移方程，而我们在$dfs$中得到的那个dfs式子[^4]，是否正是我们要求的无后效性的状态转移方程？

而且我们在记忆化搜索中做的努力也已经让这个式子递推的性质呼之欲出，只需要对这个式子[^4]稍作改动，我们就能得到我们需要的状态转移方程：
​

$dp[i]=min(dp[i-1]+|h[i]-h[i-1]|,dp[i-2]+|h[i]-h[i-2]|)$

我们只需要正着递推过去，就能得到与$dfs$和记忆化搜索一样的答案：
​

const int nmax = 200000;
int dp[nmax+10];
void solve(){
    int n;
    cin>>n;
    //初始化
    for(int i=1;i<=n;i++)cin>>h[i];
    dp[1]=0,dp[2]=abs(h[2]-h[1]);

    for(int i=3;i<=n;i++)
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));

    return void(cout<<dp[n]);
}
​

小结及其他

如果你的图论学的比较好，你会发现，状态其实是图中的节点，而状态转移方程是边。实际上我们完全可以通过已给条件来建一张图，然后根据题目需要跑一个算法，就此题来说，我们需要跑一个dij最短路，代码如下：
​

const int nmax = 200000;
struct edge{
    int v,w;
};
int h[nmax+10],d[nmax+10],n;
vector<edge>e[nmax+10];
bool vis[nmax+10];
priority_queue<pair<int,int>>q;
void dij(int s){
    //初始化
    for(int i=1;i<=n;i++)d[i]=INT32_MAX;
    d[s]=0;q.push({0,s});

    while(!q.empty()){
        auto tmp=q.top();q.pop();
        int u=tmp.second;
        if(vis[u])continue;
        //松弛操作
        vis[u]=true;
        for(auto nd:e[u]){
            int v=nd.v,w=nd.w;
            if(w+d[u]<d[v]){
                d[v]=w+d[u];
                q.push({-d[v],v});
            }
        }
    }
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];

    for(int i=1;i<=n-2;i++){//建图
        for(int j=i+1;j<=i+2;j++){
            e[i].push_back({j,abs(h[j]-h[i])});
        }
    }
    e[n-1].push_back({n,abs(h[n]-h[n-1])});

    dij(1);
    return void(cout<<d[n]);
}
​

经典 dp 介绍

背包 dp

背包dp具有以下特征：给定$N$种物品，每种物品有**一个**或**多个**或**无限个**，并且具有价值$v_{i}$和花费$w_{i}$，你现在有总费用$W$，问怎样选择物品可以获得最大价值。

更具体地说，根据每种物品的数量，我们又把背包dp分为**01背包**，**多重背包**和**完全背包**，下面一个个介绍。
​

01 背包—采药（luogu P1048）⁵

‍