一、算法介绍

1.简介

本次课我们将介绍介绍动态规划（Dynamic Programming, DP）及其解决的问题、根据其设计的算法及优化。

动态规划是编程解题的一种重要手段，它是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

2.关键术语

• 阶段：把原问题视为若干重叠子问题的逐层递进，对这若干个问题的求解过程就构成了若干个相互联系的阶段。过程不同，阶段数就可能不同。描述阶段的变量称为阶段变量，常用 $k$ 表示。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程转化为多阶段决策的过程。

• 状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。通常一个阶段有若干个状态，状态通常可以用一个或一组数来描述，称为状态变量。

• 决策：表示当过程处于某一阶段的某个状态时，可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。不同的决策对应着不同的数值，描述决策的变量称决策变量。

• 状态转移方程：动态规划中本阶段的状态往往是上一阶段的状态和上一阶段的决策的结果，由第 $i$ 段的状态 $f(i)$，和决策 $u(i)$ 来确定第 $i+1$ 段的状态。状态转移表示为 $F(i+1)=T(f(i),u(i))$，称为状态转移方程。

• 策略：各个阶段决策确定后，整个问题的决策序列就构成了一个策略，对每个实际问题，可供选择的策略有一定范围，称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。

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

3.两个性质

• 无后效性：在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。
• 最优子结构：一个最优策略的子策略，也是最优的。也就是说下一阶段的最优解应该能够由前面各阶段子问题的最优解导出。

二、实例分析

1.一个简单的例子

下面我们将以洛谷上的题目 P1216 为例，讲解动态规划算法的最简单的使用方式。

（1）题目大意

• 有一个数字三角形，我们需要从顶端走到底部
• 只能按照层次递增的方式移动，不能逆行，不能横向移动
• 当从第 $k$ 层移动到 $k+1$ 层时，只能走到左下方的点或者右下方的点
• 每一个点有一个权值，我们需要最后的权值和最大

（2）题目分析

• 原图仅供参考，我们应该结合样例来分析

• 因为只能在层与层之间移动，所以显然满足无后效性

• 只能向左下方和右下方移动对应样例的输入来看，其实意味着对于 $(i,j)$ 来说，它可以移动到 $(i+1,j)$ 和 $(i+1,j+1)$ 这两个点上

• 换一个思路，对于 $(i,j)$ 来说，只有 $(i-1,j)$ 和 $(i-1,j-1)$ 这两个点能移动到它上面

• 所以如果说我们已经得到了到点 $(i-1,j)$ 和 $(i-1,j-1)$ 这两个点上的最大总权值了，那么它们两个的最大值与 $(i,j)$ 的权值 $mp[i][j]$ 的和就时点 $(i,j)$ 的最大总权值了。满足最优子结构的特性。

• 状态转移方程为：
  $$dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+mp[i][j]$$

  • $dp[i][j]$ 表示到点 $(i,j)$ 为终点时的最大权值和
  • $mp[i][j]$表示点 $(i,j)$ 的权值

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

（3）正解代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;
typedef long long ll;
const ll maxn=1010;
ll n;
ll dp[maxn][maxn],mp[maxn][maxn];

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=i;j++)
			scanf("%lld",&mp[i][j]);
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=i;j++)
		{
			dp[i][j]=mp[i][j];
			if(i-1>=1)
				dp[i][j]=max(dp[i][j],dp[i-1][j]+mp[i][j]);
			if(i-1>=1 && j-1>=1)
				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+mp[i][j]);
		}
	}
	ll ans=-1;
	for(ll i=1;i<=n;i++)
		ans=max(ans,dp[n][i]);
	printf("%lld\n",ans);
	
	return 0;
}

2.最长上升子序列

（1）题目大意

• 给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。
• 最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

（2）题目分析

• 设数 $a[i]>a[j],i>j$，则意味着 $i$ 可以与任意以 $j$ 结尾的上升子序列组成新的上升子序列

• 那么 $i$ 能构成的最长的上升子序列就一定来源于满足条件的所有 $j$ 的最长上升子序列的最大值

• 状态转移方程为：
  $$dp[i]=max(dp[i],dp[j]+1),(i>j,a[i]>a[j])$$

  • $dp[i]$ 表示以 $i$ 结束的最长上升子序列长度

（3）正解代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll maxn=5010;
ll a[maxn],dp[maxn];
ll ans,n;
int main() 
{
	cin>>n;
	for(ll i=1;i<=n;i++)
		cin>>a[i];
	dp[0]=0;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=0;j<i;j++)
			if(a[i]>a[j])
				dp[i]=max(dp[i],dp[j]+1);
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	
	return 0;  
}

三、作业

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

B3637 最长上升子序列

P2563 [AHOI2001]质数和分解

P2437 蜜蜂路线

P1077 [NOIP2012 普及组] 摆花

P1091 [NOIP2004 提高组] 合唱队形