动态规划（一）—— 基本工具（上）第一章节之动态规划的基础(下：多维)

例题扩展及讲解

T1

n × m n\times m n×m 的方格（ n , m ≤ 2000 n,m\le 2000 n,m≤2000），第 i i i 行第 j j j 个格子的值是 a i , j a_{i,j} ai,j​。现在从第 1 1 1 行第 1 1 1 个格子出发，每一步都可以向下或向右移动一格，直到走到第 n n n 行第 m m m 个格子。问经过的格子总和最大是多少。

想想对于方格来说的一维状态？或许压维或滚动数组能做到，但从基础来说，似乎只能定义二维的状态，而这便是今天的主题。其实，二维和一维定义从本质上来说没什么区别，思考一下，是不是只需要更新走到这一格的最优解？我们想想，是不是从第一次到它就一定是最优解？是的，因为不会第二次走到它。而我们只可能从上面一个和左边一个的格子转移过来，那么得：

• 状态定义及目标函数： f ( i , j ) f(i,j) f(i,j) 表示从 ( 1 , 1 ) (1,1) (1,1) 走到 ( i , j ) (i,j) (i,j) 的最大值。
• 状态转移： f ( i , j ) = m a x { f ( i − 1 , j ) , f ( i , j − 1 ) } + a i , j f(i,j)=max\{f(i-1,j),f(i,j-1)\}+a_{i,j} f(i,j)=max{f(i−1,j),f(i,j−1)}+ai,j​
• 边界： f ( i , j ) = 0 , i ∈ [ 0 … n ] , j ∈ [ 0 … m ] f(i,j)=0,i\in[0\dots n],j\in[0\dots m] f(i,j)=0,i∈[0…n],j∈[0…m]
• 时间复杂度： Θ ( n m ) \Theta(nm) Θ(nm)
• 答案： f ( n , m ) f(n,m) f(n,m)

代码

#include <bits/stdc++.h>
using namespace std;
int a[2100][2100];

int dfs(int x, int y) {
	if (x == 1 && y == 1) {
		return a[x][y];
	}
	if (x == 1) {
		return dfs(x, y - 1) + a[x][y];
	}
	if (y == 1) {
		return dfs(x - 1, y) + a[x][y];
	}
	return max(dfs(x - 1, y), dfs(x, y - 1)) + a[x][y];
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	cout << dfs(n, m);
	return 0;
}

这便是二维方格取数，这种取数问题可以扩展到图上，或是多维情况下，咱们再来一道模型题。

T2

你有一个载重量最大为 M M M 的背包，现在有 n n n个物品，重量分别为 m 1 , m 2 , … , m n m_{1},m_{2},\ldots,m_{n} m1​,m2​,…,mn​，价值分别为 v 1 , v 2 , … , v n v_{1},v_{2},\ldots,v_{n} v1​,v2​,…,vn​，现要你装入一些物品，使得在重量不超过 M M M 的情况下，价值尽可能大，求这个最大价值。

作者太懒了，直接上代码！

#include <cstdio>

const int MAX_N = 110;
const int MAX_M = 10011;
const int INF = 1000;
int v[MAX_N], m[MAX_N], f[MAX_M][MAX_N];
int main() {
	int n, M;
	scanf("%d%d", &n, &M);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &m[i], &v[i]);
	}

	for(int i = 0; i <= M; i++)
		f[i][0] = 0;
	f[0][0] = 0;
	
	for(int i = 0; i <= M; i++){
		for(int j = 1; j <= n; j++){
			f[i][j] = f[i][j - 1];
			if(m[j]<=i&&f[i][j] < f[i - m[j]][j-1] + v[j])
				f[i][j] = f[i - m[j]][j-1] + v[j];
		}
	}

	printf("%d\n", f[M][n]);
	return 0;
}

自己理解，有更多的收获，背包问题的扩展极多， 01 01 01背包也是起源，我也会陆续更新。

思考题讲解

给定一个有 n n n （ ≤ 200 \leq 200 ≤200）个正整数的数组 { a 1 , a 2 , … , a n } \{ a_{1},a_{2},\ldots,a_{n}\} {a1​,a2​,…,an​}（ a i ≤ 200 a_{i} \leq 200 ai​≤200） 和一个整数 M M M ,求选择数组中部分数字，和为 M M M 的方案数。 当两种选取方案有一个数字的下标不一样，我们就认为是不同的组成方案。

思考题

你有一个容量为 m m m（ ≤ 5000 \le 5000 ≤5000）的背包，现在有 n n n（ ≤ 2000 \le 2000 ≤2000） 种物品，重量分别为非负整数 w 1 , w 2 , … , w n w_1,w_2,\dots,w_n w1​,w2​,…,wn​，价值分别为 v 1 , v 2 , … , v n v_1,v_2,\dots,v_n v1​,v2​,…,vn​（可能为负）。现要你装入一些物品，每种物品可以放多个，使得在重量恰好等于 m m m 的情况下，价值尽可能大。如果无解输出 no solution。

最后，希望各位大佬关注一下。