动态规划入门

引例：数字三角形

数字三角形——进阶版

有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外 每个数的左下方和右下方各有一个数。从第一行的数开始，每次可以往左下或右下走一格，直到走到三角形底端，把沿途经过的数全部加起来作为得分。如何走，使得这个得分尽量大，请输出最大得分。

很明显这是一个决策问题：每次选一个方向行走（左下/右下）。我们也能很容易的想到使用贪心算法来做：每次选择分值最大的。但是，贪心无法得到最优解：目光短浅。暴力搜索每一条路径可以吗？当然是可以的，我们使用回溯法把所有可能的路径全部列举出来，就可以从中选择出最优的一条路径。

问题分析

我们把当前处于的位置 $(i,j)$ 看成一个状态，而 $f(i,j)$ 表示从 $(i,j)$ 出发到达最底层能获得的最大得分，那么问题的答案就是 $f(1,1)$。

那么如何计算 $f(i,j)$ 呢？我们知道处于 $(i,j)$ 位置时，我们有两种决策：往左下走或往右下走。如果往左下 $(i+1,j)$ 走，那么就需要求从 $(i+1,j)$ 出发到达最底层的最大得分，即 $f(i+1,j)$，类似的往右下走也是，需要求 $f(i+1,j+1)$。两者选最大即 f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]。 (最优子结构)。

暴力搜索（回溯法）

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int a[N][N], n;

int dfs(int i, int j) { // 当前是第 i 层的第 j 个
	if (i == n) return a[i][j];
	return a[i][j] + max(dfs(i + 1, j), dfs(i + 1, j  + 1));
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> a[i][j];
		}
	}

	cout << dfs(1, 1) << endl;

    return 0;
}

当然我们也可以换一种搜索写法

int ans = 0;
void dfs(int i, int j, int v) { // v 记录从 1,1 出发到达 i,j 时的路径得分
	v += a[i][j];
	if (i == n) {
		ans = max(ans, v);
		return;
	}
	dfs(i + 1, j, v);
	dfs(i + 1, j + 1, v);
}

无论哪种方式的写法，我们都无法 AC 这道题。一个 $n$ 层的数字三角形，它的路径条数总共有 $2^{n-1}$ 个，时间复杂度时 $O(2^n)$ 的，我们只能过 5 个点。但是，如果使用上面这种写法，我们可以进行剪枝。

int ans = 0;
void dfs(int i, int j, int v) {
	v += a[i][j];
	if (i == n) {
		ans = max(ans, v);
		return;
	}
	if (v + s[i + 1] <= ans) return; // 最优性剪枝 s[i] 表示第 i 行到第 n 行每行中最大值之和
	dfs(i + 1, j, v);
	dfs(i + 1, j + 1, v);
}

剪枝之后我们能过 7 个点，还能再优化吗？

记忆化搜索

暴力的搜索每一条路径会有一个问题：重复搜索。为了避免这个问题我们可以使用记忆化搜索，记录已经搜索过的路径。

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int a[N][N], n;
int f[N][N]; // f[i][j] 记录从 i, j 出发到达第 n 层的路径数字之和的最大值

void dfs(int i, int j) { // 搜出从 i, j 出发到达第 n 层的路径数字之和的最大值
	if (f[i][j] == -1) {
		if (i == n) f[i][j] = a[i][j];
		else {
			dfs(i + 1, j);
			dfs(i + 1, j + 1);
			f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> a[i][j];
		}
	}

	memset(f, -1, sizeof f);
	dfs(1, 1); // dfs(0, 0);
	cout << f[1][1] << endl;

    return 0;
}

好了，我们完美的解决了这道题，时间复杂度 $O(n^2)$ ，现在还能再优化代码吗？

动态规划

动态规划的相关概念：

• 阶段：DP 按照时间、空间等将问题的求解过程划分为若干个相互联系的阶段。描述阶段的变量称为阶段变量。
• 状态：每一个阶段中包含的“位置”为状态。这里的“位置”可以看作每个阶段所处的客观条件或自然状态，描述状态的变量称为状态变量。
• 指标函数与最优值函数
• 决策：在某一阶段，在给定的某个状态下可以做出的若干选择即为决策，描述决策的变量称为决策变量。
• 状态转移方程：描述状态之间演变规律的方程称为状态转移方程。

动态规划（逆推）

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int a[N][N], n;
int f[N][N];

/*
状态：f[i][j] 表示从 (i,j) 出发到达第 n 层的路径权值最大值
状态转移方程：
i = n 时， f[i][j] = a[i][j]
i < n 时， f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1])
*/

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> a[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		f[n][i] = a[n][i];
	}

	for (int i = n - 1; i >= 1; i--) {
		for (int j = 1; j <= i; j++) {
			f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];
		}
	}

	cout << f[1][1] << endl;

    return 0;
}

动态规划（顺推）

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int a[N][N], n;
int f[N][N];

/*
状态：f[i][j] 表示从 (1, 1) 出发到达 (i, j) 时的路径权值最大值
状态转移方程：
i = 1 时， f[i][j] = a[1][1]
i > 1 时， f[i][j] = a[i][j] + max(f[i - 1][j], f[i - 1][j - 1])
*/

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> a[i][j];
		}
	}

	// 如果金字塔中的路径值可以为负数，则需要初始化 f，如果使用逆推则不需要额外初始化。
	// 初始化时一定要特别注意，计算左右边界点时需要用到的位置也需要初始化，注意 i j 的循环起始结束条件
	for (int i = 0; i <= n; i++) {
	    for (int j = 0; j <= i + 1; j++) {
	        f[i][j] = -1e9;
	    }
	}

	f[1][1] = a[1][1];
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + a[i][j];
		}
	}

	int ans = -1e9;
	for (int i = 1; i <= n; i++) {
	    ans = max(ans, f[n][i]);
	}
	cout << ans << endl;

    return 0;
}

认识动态规划

动态规划的五大要素

1. 最优化原理：最优子结构
2. 无后效性
3. 状态：描述最优解的结构
4. 状态转移方程：递归定义最优解的值
5. 程序实现：用记忆化搜索或迭代法求解

什么是无后效性？

无后效性有两层含义：一是指某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响，即“未来与过去无关”。二是指某阶段的状态一旦确定，则不受后续阶段状态及决策的影响，即“当前与未来无关”。由此，我们可以从图论的角度分析 DP 问题：一个 DP 问题的状态（节点）即转移（边）应该是一张有向无环图（DAG）。

动态规划求解的一般步骤

1. 划分阶段
2. 设计状态
3. 确定决策
4. 确定状态转移方程
5. 确定边界与目标解

动态规划的两种实现方式

1. 记忆化搜索
2. 递推（for 循环）

例题

洛谷 P2066：机器分配

1. 阶段划分：按照已处理的公司数量划分阶段，设阶段变量 $i$ 表示前 $i$ 家公司。
2. 设计状态：设 $f[i][j]$ 表示前 $i$ 家公司分配 $j$ 台设备能产生的最大盈利。
3. 决策：对于状态 $f[i][j]$ 决策对象为第 $i$ 家公司，考虑为第 $i$ 家公司分配多少台设备？设决策变量 $k(0\le k\le j)$ 表示为第 $i$ 家公司分配 $k$ 台设备。
4. 状态转移方程：$f[i][j]=max(f[i-1][j-k]+a[i][k])(1\le j\le m,0\le k\le j)$
5. 边界条件与目标解：
   1. 边界：$f[i][0]=0(1\le i\le n)$
   2. 目标解：$f[n][m]$

滑雪（记忆化搜索）

记忆化搜索的搜索形式决定了它“先计算后到的节点，后计算先到的节点”的性质，这恰好是 DAG 中的依赖关系：只要后继节点都已算过了，就可以处理当前节点——完全符合动态规划的转移要求！

三角形最佳路径问题