动态规划算法(DP,Dynamic Programming)是针对满足特定条件的一类问题，对各状态进行分阶段、有顺序、无重复、决策性的遍历求解。

动态规划把原问题视作若干个重叠子问题的逐层递进，每个子问题求解过程都构成一个“阶段”。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。

为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响，这就是“无后效性”。也就是，动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题的“状态”，图中的边则对应状态之间的“转移”，转移的选取就是动态规划中的“决策”。

很多情况下，动态规划用于求解最优化问题，下一个阶段的最有解应该能够由前面各阶段的最优解导出。这个条件被称为“最优子结构”。

“状态”、“阶段”、“决策”是构成动态规划算法的三要素，而“子问题重叠”“无后效性”和“最优子结构”是问题能用动态规划求解的三个基本条件。

子问题重叠：子问题与原问题结构相似，规模小些，计算步骤方法完全一样；原问题可以多次重复计算子问题得到。“子问题重叠”就意味着动态规划可以从小问题出发递推求解出大问题，也可以利用递归从大问题出发，递归求解小问题，直到边界，可以利用记忆化“空间换时间”的思想优化，这就是“记忆化搜索”。

最优子结构：大问题的最优解是由小问题的最优解得到的，小问题最优解可以推导大问题的最优解。

将当前阶段与前一个阶段用数学公式建立起联系，这个数学公式就是“状态转移方程”，转移可以是之前阶段对应的状态值推到当前阶段状态值，也可以是当前阶段状态值推到以后阶段对应的状态。

我们使用一道例题来学习动态规划的入门知识：

经典题目：数字三角形 Number Triangles

观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

        7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5 

在上面的样例中,从 7→3→8→7→5 的路径产生了最大。

【思路点拨】

首先，贪心做法“从上往下，始终选择当前最大的分支去走”是不对的，在选择的时候上面较小而选择走其他路径，而这条路径后面有一个或多个比较大的值，也就是贪心“鼠目寸光”。

暴力遍历每一条路径，时间复杂度为 $2^n$ ( $n$ 为数塔的高度)，会超时。参考代码如下：

#include<bits/stdc++.h>
using namespace std;
int r;int a[1001][1001];
int ans=-1;
void dfs(int i,int j,int sum){
	if(i==r+1)
	{
		ans=max(sum,ans);
		return;
	}
	dfs(i+1,j,sum+a[i][j]);
	dfs(i+1,j+1,sum+a[i][j]);
}
int main(){
	scanf("%d",&r);
	for(int i=1;i<=r;i++)
	   for(int j=1;j<=i;j++)
	      scanf("%d",&a[i][j]);
    dfs(1,1,0);    
    printf("%d",ans);
return 0;	
 } 

暴力超时的原因就是，每次计算一个状态点的值，都需要递归到最后一层，这样曾经计算过得值就要重新计算一次，我们可以采用记忆化搜索，记录算过的状态值。

方法一：记忆化搜索，函数 $dfs(i,j)$ 返回值表示从 $(i,j)$ 出发到达最后一层路径数字和的最大值，那么 $dfs(i,j)= max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j]$ , 可以利用数组记录 $dfs(i,j)$ 的值（因为下次调用的时候直接使用）。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N],f[N][N];
int r;
int dfs(int i,int j){
	if(f[i][j]!=-1)return f[i][j]; //如果算过了，就直接放回
	if(i==r)return f[i][j]=a[i][j]; //递归边界
	return f[i][j]=max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j]; 
 } int main(){
	cin>>r;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=i;j++)
			cin>>a[i][j];
	memset(f,-1,sizeof(f));//-1 表示状态未被计算过 
	cout<<dfs(1,1);
	return 0;
}

当然，也可以从最后一行往上递归，尝试写一写。

提示：方法二，记忆化搜索，$dfs(i,j)$表示从第$(1,1)$走到$(i,j)$路径上的数字和的最大值。 $dfs(i,j)=max(dfs(i-1,j-1),dfs(i-1,j))$

这个问题中，我们发现当前状态的最优值，是建立在前一个阶段几个“子问题”最优基础上的，这就是动态规划。 动态规划是求类最优的问题的方法，利用问题可以划分成与原问题相似的子问题，将原问题视作若干个重叠子问题逐层递进，每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。

为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响，也就是“无后效性”。

动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。有向无环图中节点对应问题中的“状态”，图中的边则对应状态之间的“转移”，转移的选取就是动态规划中的“决策”。

下一个阶段最优解应该能够由前面各阶段子问题的最优解导出，这个条件就是“最优子结构”。

“状态”“阶段”“决策”是构成动态规划算法的三要素，“子问题重叠性”“无后效性”“最优子结构性质”是问题能够用动态规划求解的三个基本条件，也是分析问题的切入口。

动态规划算法把相同的计算过程作用于各阶段同类子问题，状态之间的装换关系可以用一个数学方程表示，这就是“状态转移方程”。一般求解动态规划，分成这几个关键步骤：

（1）定义状态，就是求解问题抽象化描述。例如“数字三角形”中定义 $f[i][j]$ 表示从最底层走到 $(i,j)$ 路径上数字和的最大值。这一步尤为重要，定义的状态应该具备“子问题重叠性”、“无后效性”、“最优子结构”，状态定义混淆，往往是求解这类问题失败的原因。

（2）状态转移方程，就是用比较严谨的数学语言描述当前状态，与前一个阶段状态间的关系，也就是与子问题间的关系，往往选择一个最优的子问题进行转移。

（3）转移顺序，一般可以分成“顺推”和“逆推”。“顺推”就是从已知要位置一步一步递推，要求当前阶段全部求解完后，才能求下一个阶段，本质就是在拓扑序上顺序求解。在实际编程中，往往忽略转移顺序出现“当前要计算的值，需要用到前一个阶段的值，而前一个阶段的值都没有计算过”这种错误。很多问题阶段划分不是很明显，需要先进行拓扑排序。 如果搞不清阶段间的前后顺序，可以“逆推”，也就是递归求解，状态对应的值需要记录，以方便后面重复使用提高效率，这就是记忆化优化，也就是计算化搜索。

(4)明确边界（起点的值）

(5)目标。

以“数字三角形”为例，我们进行分析：

方法三:动态规划-从下往上

（1）定义状态，$f[i][j]$ 表示从下往上走到 $(i,j)$ 路径上数字和的最大值。

（2）状态转移方程，$f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j]$

（3）转移顺序：本问题阶段划分很清晰，每一层就是一个阶段，层数 $i$ 的变化应该从大到小。

（4）边界：最下面一层 $f[n][j]=a[n][j]$ ，也就是起点。

（5）目标：$f[1][1]$

方法四：动态规划-从上往下

（1）定义状态，$f[i][j]$ 表示从上往下走到 $(i,j)$ 路径上数字和的最大值。

（2）状态转移方程，$f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]$

（3）转移顺序，阶段划分清晰，层数$i$应该从小到大。

（4）边界：$f[1][1]=a[1][1]$，目标 $max(f[n][1],f[n][2]...f[n][n])$

动态规划的艺术在于状态设计和问题与子问题之间的转移，如何把问题抽象成状态空间，进一步抽象成 $DP$ 的状态表示，往往考察选手的智力水平，通过大量练习可以提升这方面的能力。

---

经典模型

模型1：最长上升子序列 $LIS$

问题描述：给定一个长度为 $N$ 的数列 $A$ ，求数值单调递增的子序列的长度最长是多少。$A$ 的任意子序列 $B$ 可表示为 $B=\{A_{k_1},A_{k_2},...,A_{k_p}\}$，其中$k_1<k_2<...<k_p$ 。

定义状态：$F[i]$ 表示以 $A[i]$ 为结尾的“最长上升子序列”的长度

状态转移方程：$F[i]=max(F[j]+1)(0 \leq j<i,A[j]<A[i])$

转移顺序：阶段划分明显，从序列开始，从前到后 边界：$F[1]=1$

目标：$ans=max\{F[i]\} (1\leq i \leq N)$

时间复杂度：$O(N^2)$

优化：转移过程实际是去前面找一个能接的最长子序列，然后接上，如果前面最长子序列用一个单调递增的数组维护，利用二分查找，可以 $O(\log{N})$ 找到第一个大于等于或第一个大于（求严格单调递增 $LIS$ ）的位置，如果这个位置没有超过序列的长度，那直接更新这处的值，否则新增递增序列的长度插入到末尾，这样递增序列的最长长度就是答案，复杂度为 $O(N\log{N})$ 。数据结构也可以进行优化。

模型2：最长公共子序列 $LCS$

问题描述：给定两个长度分别是 $N$ 和 $M$ 的字符串 $A$ 和 $B$，求既是 $A$ 的子序列又是 $B$ 的子序列的字符串长度最长是多少。

状态定义：$F[i][j]$ 表示前缀子串 $A[1\dots i]$ 与 $B[1 \dots j]$ 的“最长公共子序列”的长度。

状态转移方程：$F[i][j]=max\{ F[i-1][j] , F[i][j-1] , if(A[i]==B[j])F[i-1][j-1] \}$

转移顺序：$i$ 从小到大，$j$ 从小到大

边界：$F[i][0]=F[0][j]=0$

目标：$F[N][M]$

模型3：$DAG$ 上最长路和最短路

问题描述：给定一个 $DAG$ 图 ( $DAG$ ，也就是 Directed Acyclic Graph 有向无环图。),求图中最长路或最短路。

---

经典例题

单篇博客内容太长，已经拆分，请参考“经典例题”、“课后练习”

---

学习完毕

{{ select(1) }}

• YES
• NO