动态规划

背包问题

01背包模版

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int f[N];
int v[N], w[N];

int main() {
	int N, V;
	cin >> N >> V;

	for (int i = 1; i <= N; i++) cin >> v[i] >> w[i];

	for (int i = 1; i <= N; i++)
    // v倒序输出，防止数据覆盖(因为这里采用滚动数组，用到n-1的值)
		for (int j = V; j >= v[i]; j--)
			f[j] = max(f[j], f[j - v[i]] + w[i]);

	cout << f[V] << endl;

	return 0;
}

完全背包模版

• 内层循环正向进行，其他与01背包一致

多重背包(朴素)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int s[N], v[N], w[N];
int f[N];

int main() {
	int N, V;
	cin >> N >> V;
	for (int i = 1; i <= N; i++) cin >> v[i] >> w[i] >> s[i];

	for (int i = 1; i <= N; i++) {
		for (int j = V; j >= v[i]; j--) {
			for (int k = 1; k <= s[i]; k++) {
				if(j >= k * v[i])
					f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
			}
		}
	}

	cout << f[V] << endl;

	return 0;
}

多重背包(二进制优化)

• 思路：通过个数的二进制表示，转化为01背包

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int v[N], w[N];
int f[M];

int main() {
	int N, V;
	cin >> N >> V;

	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		int a, b, s;
		cin >> a >> b >> s;

		int k = 1;
		while (k <= s) {
			cnt++;
			v[cnt] = k * a;
			w[cnt] = k * b;
			s -= k;
			k *= 2;
		}

		// 还有剩余则再进行打包
        if (s) {
			cnt++;
			v[cnt] = s * a;
			w[cnt] = s * b;
		}
	}
	N = cnt;

	for (int i = 1; i <= N; i++) {
        // 变成01背包问题后记得倒序
		for (int j = V; j >= v[i]; j--) {
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}

	cout << f[V] << endl;

	return 0;
}

分组背包问题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int f[N], s[N];
int v[N][N], w[N][N];

int main() {
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		for (int j = 1; j <= s[i]; j++) {
			cin >> v[i][j] >> w[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
        // 每组最多选一个，故背包容量倒序
		for (int j = m; j >= 0; j--) {
			for (int k = 1; k <= s[i]; k++) {
				if(j>=v[i][k])
					f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
			}
		}
	}

	cout << f[m] << endl;

	return 0;
}

线性DP

数字三角形

• 特别注意边界问题的处理

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N], f[N][N];

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

	// 为下面递推方便，i从0 ~ n
    for (int i = 0; i <= n; i++) {
        // j 从 0 到 i + 1
		for (int j = 0; j <= i + 1; j++) {
			f[i][j] = -INF;
		}
	}

	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 - 1], f[i - 1][j]) + a[i][j];
		}
	}

	int res = -INF;
	for (int i = 1; i <= n; i++) res = max(res, f[n][i]);

	cout << res << endl;

	return 0;
}

最长上升子序列(朴素)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
// f 表示以 i 结尾的递增子序列最长长度
int f[N], a[N];

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

	for (int i = 1; i <= n; i++) {
        // 初始化：至少长度为 1
		f[i] = 1;
		for (int j = 1; j < i; j++) {
			if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
		}
	}

	int res = 0;
	for (int i = 1; i <= n; i++) res = max(res, f[i]);

	cout << res << endl;

	return 0;
}

最长上升子序列(二分法优化)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
// q 表示长度为 r 的子序列中结尾最小的
int a[N], q[N];

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

	int len = 0;
	for (int i = 1; i <= n; i++) {
		int l = 0, r = len;
		while (l < r) {
			int mid = l + r + 1 >> 1;
			if (q[mid] < a[i]) l = mid;
			else r = mid - 1;
		}
		len = max(len, r + 1);
		q[r + 1] = a[i];
	}

	cout << len << endl;

	return 0;
}

最长公共子序列

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
	cin >> n >> m >> a + 1 >> b + 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
            // 不管i , j 位是否相同， 都先从分别回退一位中取最大值
			f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			if (a[i] == b[j])
            // 若相同， 再跟都回退一位基础上加上一比较
				f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		}
	}

	cout << f[n][m] << endl;

	return 0;
}

最短编辑距离
思路: 和最长公共子序列类似，不过递推规则有变动， 还要讨论该位不相同的变化

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
	cin >> n >> a + 1 >> m >> b + 1;

	for (int i = 1; i <= n; i++) f[i][0] = i;
	for (int j = 1; j <= m; j++) f[0][j] = j;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
            // 分别回退要加一(删除)
			f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            // 相同则只需比现在和均回退一位的情况
			if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            // 否则两位需要改成一致，加一
			else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
		}
	}

	cout << f[n][m] << endl;

	return 0;
}

编辑距离

• 思路: 将最短编辑距离中的计算函数封装起来即可

区间合并

合并石子

• 和哈夫曼树的区别： 本题要求每次只可合并相邻堆

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
int a[N], s[N];
int f[N][N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
    // 预处理，计算前缀和
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

	// 外层循环枚举区间长度
    for (int len = 2; len <= n; len++) {
        // 内层循环枚举起点
		for (int i = 1; i <= n - len + 1; i++) {
			int l = i, r = i + len - 1;
            // 初始值设为无穷大
			f[l][r] = 1e8;
            // k 的范围为 l 到 r - 1 ， 因为 k + 1 < r
			for (int k = l; k < r; k++) {
                // 最后面要加上 s[r] - s[l - 1] ，前缀和计算这段新的合并代价
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
			}
		}
	}

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

	return 0;
}

计数类DP

整数的划分

• 思路：转化为完全背包问题

#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];

int main() {
	cin >> n;

	f[0] = 1;
	// 滚动数组： f[i][j] = f[i - 1][j] + f[i][j - 1];
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			f[j] = (f[j] + f[j - i]) % mod;
		}
	}

	cout << f[n] << endl;

	return 0;
}

数位统计DP

• 思路： 分类讨论和前缀和(遇到不易直接计算的都转化为前缀和处理，即1 ~ n的情况)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 获得 l 到 r 的数字(从左向右看)
int get(vector<int> num, int l, int r) {
	int res = 0;
	for (int i = l; i >= r; i--) res = res * 10 + num[i];
	return res;
}

int power10(int n) {
	int res = 1;
	while (n) res *= 10, n--;
	return res;
}

int count(int n, int x) {
	vector<int> num;
	while (n) {
		num.push_back(n % 10);
		n /= 10;
	}
	n = num.size();

	int res = 0;
	for (int i = n - 1 - !x; i >= 0; i--) {
		// 第一种情况： 前面的数在1 ~ abc -1 之间
		if (i < n - 1) {
			// 前面的数字乘上后面随便取
			res += get(num, n - 1, i + 1) * power10(i);
			if (!x) res -= power10(i);
		}

		// 该位正好一样，卡住了，则后面可取0 ~ def (加1是0全0的情况)
		if (num[i] == x) res += get(num, i - 1, 0) + 1;
		// 比该位小，后面随便取
		else if (num[i] > x) res += power10(i);
	}

	return res;
}

int main() {
	int a, b;
	while (cin >> a >> b, a) {
		// 由于下面默认b > a， 故若 a > b 需要换序
		if (a > b) swap(a, b);
		for (int i = 0; i <= 9; i++) {
			// 前缀和思想
			cout << count(b, i) - count(a - 1, i) << " ";
		}
		cout << endl;
	}

	return 0;
}

状态压缩DP

• 思路: 由于每列的情况跟列的序号无关，故可以单独判断

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << N;

int n, m;
// f 为第 i 列 第 j 种状态(二进制) 的可行方案数
LL f[N][M];
// st 表示当前列所有连续空格是否均为偶数个，否则不对
bool st[M];
vector<int> state[M];

int main() {
	while (cin >> n >> m, n || m) {
		for (int i = 0; i < 1 << n; i++) {
			int cnt = 0;
			bool is_valid = true;
			for (int j = 0; j < n; j++) {
				// 某位被占用，连续的一段结束，结算
				if (i >> j & 1) {
					// 出现奇数个空格，不对
					if (cnt & 1) {
						is_valid = false;
						break;
					}
                    置零，重新开始计数
					cnt = 0;
				}
				else cnt++;
			}
			// 最后一段可能未遇到障碍，故仍需检查
			if (cnt & 1) is_valid = false;
			st[i] = is_valid;
		}

		for (int i = 0; i < 1 << n; i++) {
			// 注意清空，state[i] 表示 i (二进制情况) 下可作为来源的各个状态
			state[i].clear();
			for (int j = 0; j < 1 << n; j++) {
				// i & j 表示所有位都没有冲突，即不出现同时在该位的情况
				// i | j 表示 i 和 j 共同作用后的状态仍满足st
				if ((i & j) == 0 && st[i | j]) {
					state[i].push_back(j);
				}
			}
		}

		memset(f, 0, sizeof f);
		f[0][0] = 1;
		// 遍历所有列
		for (int i = 1; i <= m; i++) {
			// 对于该列所有状态找前面可转移的状态
			for (int j = 0; j < 1 << n; j++) {
				// 遍历 j 符合条件的前置状态
				for (auto k : state[j]) {
					f[i][j] += f[i - 1][k];
				}
			}
		}

		// 输出第 m 列， 没有任何一格被前一列占用
		cout << f[m][0] << endl;
	}

	return 0;
}

最短Hamilton路径

• 注意事项：1. 二进制表示一律用 0-indexed (由二进制本身决定) 2.不要忘记初始化

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 20, M = 1 << N;

int n;
// f 记录在 i (二进制) 状态下， 到达点 j 的最短距离， w 记录两点之间距离(注意i 记录所有情况，未必遍历所有点)
int f[M][N], w[N][N];

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

	// 最短路问题初始化距离为无穷大
	memset(f, 0x3f, sizeof f);
	// 设定出发点，从0出发经过1到0的路为0
	f[1][0] = 0;
	for (int i = 0; i < 1 << n; i++) {
		for (int j = 0; j < n; j++) {
			// 当前路径 i 要 经过点 j
			if (i >> j & 1) {
				for (int k = 0; k < n; k++) {
					// 当前路径i 要经过点 k
					if (i >> k & 1) {
					// i 到 j 的最短路 = min(i 不经过 j 到 k 的最短路加上 k 到 j 的距离， 原先值)
					// i - 1 << j 表示去除 i 中经过 j 的所有路(因为原先经过j ，故将该位减去即置零，就是不经过)
						f[i][j] = min(f[i - (1 << j)][k] + w[k][j], f[i][j]);
					}
				}
			}
		}
	}

	// 答案为经过所有点(111...1) ，最后到 [n - 1] 的最短路径
	cout << f[(1 << n) - 1][n - 1] << endl;

	return 0;
}

树形DP

没有上司的舞会

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 6010;

int n;
// f 的第一个维度代表编号，第二个维度代表选/不选
int f[N][2], happy[N];
bool has_father[N];
int h[N], e[N], ne[N], idx;

// 用领接表存上司——下属关系
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
	// 当自身参与时，开心值至少有自己的
	f[u][1] = happy[u];

	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		// 将下面的子节点全部探索完毕
		dfs(j);

		// 
		f[u][1] += f[j][0];
		// 自己不参加，则加上下属参加/不参加中较大的那个
		f[u][0] += max(f[j][0], f[j][1]);
	}
}

int main() {
	cin >> n;
	// 不要忘了初始化邻接表
	memset(h, -1, sizeof h);

	for (int i = 1; i <= n; i++) cin >> happy[i];

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		// 注意 b 是 a 的父节点，要倒过来(新添加的是原节点的子节点)
		add(b, a);
		has_father[a] = true;
	}

	// 找出祖宗节点：没有父节点者
	int root = 1;
	while (has_father[root]) root++;

	// 从祖宗节点开始探索
	dfs(root);
	// 取祖宗参与 / 不参与的最大值
	cout << max(f[root][0], f[root][1]) << endl;

	return 0;
}

记忆化搜索

滑雪

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 310;

int n, m;
int f[N][N], g[N][N];

int dfs(int x, int y) {
	// 用引用方便后面写
	int& v = f[x][y];
	// 若已计算过，直接返回
	if (v != -1) return f[x][y];

	// 方向数组
	int dx[] = { -1,0,0,1 };
	int dy[] = { 0,-1,1,0 };

	v = 1;
	for (int i = 0; i < 4; i++) {
		int a = x + dx[i], b = y + dy[i];
		// 要求： 不越界且比当前地势低才可到达
		if (a > 0 && a <= n && b > 0 && b <= m && g[a][b] < g[x][y]) {
			// 满足条件则取当前值和(a,b) 点经过最大路径长 + 1
			v = max(v, dfs(a, b) + 1);
		}
	}

	return v;
}

int main() {
	cin >> n >> m;
	memset(f, -1, sizeof f);

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

	int res = 0;
	// 每个点都试试，不知道从哪出发最大
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			res = max(dfs(i, j), res);
		}
	}

	cout << res << endl;

	return 0;
}