1.概念

DP 即动态规划($\color{red}{\text{D}}$$\color{black}{\text{ynamic}}$ $\color{red}{\text{P}}$$\color{black}{\text{rogramming}}$)，是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。

看不懂？很正常。下面我们来通俗地理解一下 DP。

2. DP的通俗理解

我们来看一个例子。比如一个公司的经理要撤职，所以找他的下属员工里业绩最好的人来代替他。所以他就跟他的三个副经理说：你把你下属最好的员工告诉我，然后他就会在这些推荐的人中选出一个最好的。同样地，副经理也会跟他的三个总管说，总管又会和三个副总管说，直到下分到员工，那么他就会推荐他自己。

所以说，DP 的核心思想是把原问题分解成子问题进行求解，也就是分治的思想。

那么 DP 满足什么性质呢？首先是可推导，也就是说最优解可以通过最优子解推导而来；还有就是无后效，也即为求出来的最优子结果不会随着后面推出来的最优解而改变。

想想，在数学中，什么东西满足这两个性质呢？我们自然就会想到数列的递推方程。比如斐波那契数列 $F$，就满足 $F_n=F_{n-1}+F_{n-2}$。这东西显然可推导，同时也具备无后效性质。

3.DP 的过程

对于上面的例题，我们来进行如下步骤的分析：

• 划分子问题。对于每一个人，他都会和他的三个直接下属要最好的人。所以这就把问题划分为小的子问题了。
• 建立状态。我们假设对于每一人 $i$，他下属最好的员工为 $f_i$。
• 状态转移。设每个人 $i$ 的下属组成的集合为 $V$。那么 $f_i=\text{max}\{f_u\ \text{s.t.}\ u\in V\}$。这个很好理解。
• 初始化/确定边界条件。因为这样不断递推下去，还是没有一个结果。所以说还要定义边界条件，也就是对于每一个员工 $j$，$f_j$ 都是这个员工本身。

4.简单 DP 问题

动态规划是信息学中比较难熟练掌握的算法，因为它变化多端。我们先看一道非常简单的例题，用于理解。

例1 有 $n$ 阶台阶，每次可以跳 $1$ 个或 $3$ 个，那么从第 $0$ 阶到第 $n$ 阶有多少种不同的方式？$n\le 10^6$。

解答：首先，划分子问题，对于第 $i$ 阶台阶，从开始跳到这里的情况无非就是两种情况：1）先跳到第 $i-1$ 阶，再跳到 $i$ 阶；2）先跳到 $i-3$ 阶，再直接跳三个到 $i$ 阶。

然后建立状态和状态转移就比较简单了：设跳到第 $i$ 阶台阶的方案数为 $f_i$，那么 $f_i=f_{i-1}+f_{i-3}$。

那么怎样初始化呢？首先，$f_0$ 必然等于 $1$。但这样就够了吗？考虑 $i=1$ 的情况，则 $f_1=f_0+f_{-2}$。然而 $f_{-2}$ 是没有意义的，所以我们还需要初始化 $f_1=f_2=1$。综上，我们就进行完了所有的步骤，就差实现代码了。

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n;
int f[N];
int main(){
    scanf("%d",&n);
    f[0]=f[1]=f[2]=1;
    for(int i=3;i<=n;i++) f[i]=f[i-1]+f[i-3];
    printf("%d\n",f[n]);//最后求的结果就是f[n]，即为从开始到第n阶的方案数
    return 0;
}

到此，你是不是掌握了 DP 题目的基本思路？现在来一些练习题吧：P1091 合唱队形，P1077 摆花，P1439 【模板】最长公共子序列。

这三道题难度递增。第二道题的状态转移方程可能就不是一维的了，也许是 $f_{i,j}$，你需要考虑 $i,j$ 代表什么更好一些；第三题就更复杂了，你需要在推出来的 DP 方程基础上再优化，才能解决问题。

练习1：P1091 合唱队形
这道题很容易想到最终的合唱队形中 $T_i$ 是最特别的，所以我们不妨枚举 $i$ 的取值。对于每个 $i$，需要求的是 $1-i$ 中的最长上升子序列长度和 $i-n$ 中最长下降子序列长度，并且这两个序列必须包含 $i$。

这样我们容易想到定义两个状态：$f_i$ 表示 $1-i$ 中包含 $i$ 的最长上升子序列长度，$g_i$ 表示 $i-n$ 中包含 $i$ 的最长下降子序列长度。

我们先看 $f_i$ 如何转移。对于任意的 $j<i$，如果 $T_j<T_i$，那么 $1-i$ 中包含 $i$ 的最长上升子序列的倒数第二项就有可能是 $T_j$，此时就更新 $f_i=\max\{f_i,f_j+1\}$。

同样地，对于任意的 $j>i$，如果 $T_j<T_i$，那么更新 $g_i=\max\{g_i,g_j+1\}$。

初始化什么呢？容易知道，$f_0=0,g_{n+1}=0$。

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n;
int a[N];
int f[N],g[N],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    	for(int j=0;j<i;j++) 
			if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
    for(int i=n;i>=1;i--)
    	for(int j=n+1;j>i;j--) 
			if(a[i]>a[j]) g[i]=max(g[i],g[j]+1);
    for(int i=1;i<=n;i++) ans=max(f[i]+g[i]-1,ans);
    //ans表示队形中最多有多少人
    //枚举每一个节点，答案就是f[i]+g[i]-1
    //可以理解成，第i人作为最高的那个人
    //那么左边最多有f[i]-1人，右边最多g[i]-1人，总和f[i]+g[i]-1人
    cout<<n-ans<<endl;
    return 0;
}

练习2：摆花

首先容易想到要定义第 $i$ 位这个维度。但是这还不够，所以我们再定义一个维度：设 $f_{i,j}$ 为前 $i$ 位用 $j$ 朵花的方案数。

那么容易知道，第 $i$ 位可以放 $0-a_i$ 朵花，进而 $f_{i,j}=\sum\limits_{k=0}^{a_i} f_{i-1,j-k}$，意思就是前 $i-1$ 位可以放 $j-a_i$ 到 $j$ 朵花。注意 $j-a_i$ 可以小于 $0$，此时就不用枚举这种情况了。

初始化什么呢？显然，当 $j=0$ 时，$f_{i,j}=1$。

#include<bits/stdc++.h>
#define MOD 1000007 
using namespace std;
const int N=105;
int n,m;
int f[N][N];
int a[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=0;i<=n;i++) f[i][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=max(j-a[i],0);k<=j;k++)
				f[i][j]=(f[i][j]+f[i-1][k])%MOD;
		}
	}
	printf("%d\n",f[n][m]);//最后的所求就是f[n][m]，代表前n个位置放m朵花的方法数
}

练习3：最长公共子序列

首先来定义：第一个序列第 $i$ 个位置上的数是 $a_i$，第二个序列为 $b_i$。设 $b_i$ 与 $a_j$ 相等，那么定义 $t_i=j$。所以说对于任意的 $i<j$，如果 $t_i<t_j$，那么 $b_i$ 和 $b_j$ 就可以在一个公共子序列中。这样，我们就把问题转化为了：求 $t$ 数组的最长上升子序列长度。

那不就简单了嘛！练习一刚刚讲过如何求最长上升子序列，直接套一个模板就行了。但这真的可以吗？练习一中我们给出的算法是 $O(n^2)$ 效率的，这道题里的 $n\le 10^5$，显然会超时。是时候想一些优化算法了。

设 $f_i$ 为序列中长度为 $i$ 的上升子序列最后一位最小是多少。比如 $\{1,4,2,3,5\}$ 这个序列，$f_3=3$。容易知道，$f$ 数组是单调不减的。所以说每次找到一个最大的 $k$，使得 $f_k<a_i$，然后更新 $f_{k+1}=a_i$ 即可。寻找 $k$ 可以用二分查找，时间复杂度 $O(\log n)$。

#include<bits/stdc++.h>
#define INF 2147483647
using namespace std;
const int N=100005;
int n;
int a[N],b[N];
int t[N];
int f[N];
int mx,l,r,mid,position;//二分查找需要
//mx代表最大的数使得f[mx]不为INF，也即题目所求值
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++){
		t[a[i]]=i;
		f[i]=INF;//初始化f数组为无穷大，因为要求最小值
	}
	for(int i=1;i<=n;i++){
		if(f[mx]<t[b[i]]) mx++,f[mx]=t[b[i]];//如果需要更新mx，就直接更新
		else{//否则，二分查找需要更新的位置
			l=0,r=mx,position=0;//左端点为0，右端点就是mx，position记录当前搜索到的最大答案
			while(l<r){
				mid=(l+r)>>1;//取中间点，相当于(l+r)/2
				if(f[mid]>t[b[i]]) r=mid;//mid不满足要求，故mid~r均不满足要求
				else position=mid+1,l=mid+1;//如果mid满足要求，则记录mid+1，l-mid就不用搜索了
			} 
			f[position]=min(f[position],t[b[i]]);//更新答案
		}
	}
	printf("%d\n",mx);//最后输出mx即可
}

总结一下，例题可以说是非常简单，但是三道练习题是各有各的难度，最后一道题更是考验了对算法的优化能力。这几道题初学者不一定要直接想出来，正如大部分 DP 的题目，需要较长时间的构思才能有思路。之后小编会讲一些常见 DP 方法，帮助更快找到思路，但是仅是方法而已，需要更多的实践。