规划之神——DP的魅力

DP就是众所周知的动态规划算法，是通过把问题分阶段完成的一种算法。

容易混淆的，分治算法。我们可以这样理解：分治算法是把问题分块完成，利用问题可划分性和子问题的相似性解题。 而动态规划则是把问题分阶段完成。

举个简单的例子：如果我们要给一根绳子染色，分治算法是把一根绳子剪成好几段，分块染色，最后拼成一根彩绳；动态规划算法则是从这根绳子的头染色，到特定长度后换颜色，重复操作到绳尾。

~~这时某些蒟蒻会问了：~~ DP和递推的代码不是一样的吗？为什么有些题是递推，有些题是名字高大上的动态规划。

我们首先要辨析：递推是指，解题过程中每一步都用同样的选择转移。而动态规划就不同，可以在选择转移过程中做出新的决策。

那么，怎么使用DP呢，我们可以分成如下三个步骤（即动态规划三要素）：

1、分析状态

俗话说：“知己知彼方能百战百胜。”我们首先要从题目中提炼出解题过程中数据的状态，判断使用什么数据结构的动态规划更适合题目。以P1006 [NOIP 2008 提高组] 传纸条为例，本题一共有两个“主人公”，按常理说我们需要用两个DP来完成；可转念一想，它要求所选路径不能重复非常之荆手。这时，我们不妨大胆一点，既然二维数组只能表示一个纸条的坐标的话——四维数组即可表示两个纸条的坐标。由此我们就可以得到

f[i][j][x][y]

,其中前两维表示第一个纸条的坐标，后两维表示第二张纸条的坐标。

2、分析阶段

某些蒟蒻此时一头雾水：“四维数组？那我们怎么用啊。”诶，我还真有一计，我们只需要 ~~四个循环(TLE警告)~~ 三个循环，由“此” ~~省略了一些步骤~~ 我们可以得出第四个数。我们从上一览“状态”中可以得出，当前决策数即为

f[i][j][x][y]

，这就是当前的“阶段”。理解了阶段，我们就可以进行下一步：

3、分析决策

不难发现，本题中决策数:

f[i][j][x][y] = max(f[i-1][j][x-1][y], f[i-1][j][x][y-1], f[i][j-1][x-1][y], f[i][j-1][x][y-1]) + a[i][j] + a[x][y]

借助这个例子，不难理解，此刻的决策就是比较上个阶段中哪个最大。~~嗯对不想写了~~ 我们就得到了STD（标程）：

CPP

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn (int)(60)
using namespace std;
ll m, n;
ll a[maxn][maxn], f[maxn][maxn][maxn][maxn];
int main() {
	cin >> m >> n;
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			for(int x = i+1; x <= m; ++x) {
				int y = i+j-x;
				if(y < 1)
					break;
				f[i][j][x][y] = max({f[i-1][j][x-1][y], f[i-1][j][x][y-1], f[i][j-1][x-1][y], f[i][j-1][x][y-1]}) + a[i][j] + a[x][y];
			}
		}
	}
	cout << f[m-1][n][m][n-1];
	return 0;
}

结语：DP有三个特点——最优化原理、无后效性、有重叠子问题

满足这三个特点的算法一定可以使用dp算法

祝屏幕前： 生活顺利

动态规划初步介绍

文章操作