动态规划
概述
从初始状态出发，经过一系列的状态转移到达目标状态，求最优值、方案数、概率
- 状态转移必须有反向，且整体不能成环
- 状态个数在可接受范围内
和搜索有点相像，因为很多算法都是围绕状态和状态转移展开的
说白了就是站在全局视角思考最好的决策
无后效性，最优状态只与之前的阶段有关，与之后的状态无关
代码实现方式
以数字三角形为例
逆推
该状态可以转移到哪些状态
vector<vector<int>> dp(n, vector<int>(n));
for (int i = 0; i < n; i ++) {
for (int j = 0; j <= i; j ++) {
if (i == 0) dp[i][j] = w[i][j];
else if (j == 0) dp[i][j] = dp[i - 1][j] + w[i][j];
else if (j == i) dp[i][j] = dp[i - 1][j - 1] + w[i][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + w[i][j];
}
}
cout << *max_element(dp[n - 1].begin(), dp[n - 1].end()) << endl;
顺推
该状态可以从哪些状态转移而来
要把初始状态单拎出来
不需要遍历目标状态，因为末尾状态不会发生转移
需要将所有状态设置初始值
vector<vector<int>> dp(n, vector<int>(n));
dp[0][0] = w[0][0];
for (int i = 0; i + 1 < n; i ++) {
for (int j = 0; j <= i; j ++) {
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + w[i + 1][j]);
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + w[i + 1][j + 1]);
}
}
cout << *max_element(dp[n - 1].begin(), dp[n - 1].end()) << endl;
记忆化搜索
或许会被归为搜索，但实际是动态规划的一种实现方式
auto dp = vector(n, vector<int>(n, -1)); // 初始值设为不可能出现的值
auto dfs = [&](auto& self, int i, int j) {
auto &res = dp[i][j];
if (res != -1) return res;
if (i == 0) return res = w[i][j];
if (j == 0) return res = self(self, i - 1, j) + w[i][j];
if (j == i) return res = self(self, i - 1, j - 1) + w[i][j];
return max(self(self, i - 1, j - 1), self(self, i - 1, j)) + w[i][j];
};
int ans = 0;
for (int j = 0; j < n; j ++) {
ans = max(ans, dfs(dfs, n - 1, j));
}
cout << ans << endl;
拓扑搜索
// 统计每个点的入度
auto in_degree = vector(n, vector<int>(n, 0));
for (int i = 0; i + 1 < n; i ++) {
in_degree[i + 1][j] ++;
in_degree[i + 1][j + 1] ++;
}
auto dp = vector(n, vector<int>(n, 0));
queue<pair<int, int>> q;
// 将入度为0的点加入队列，并计算他的值
for (int i = 0; i < n; i ++) {
for (int j = 0; j <= i; j ++) {
if (in_degree[i][j] == 0) {
q.emplace(i, j);
dp[i][j] = w[i][j];
}
}
}
pair<int, int> dirs[2] = {{1, 0}, {1, 1}};
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (auto [dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (x == n) continue;
dp[x][y] = max(dp[x][y], dp[i][j] + w[x][y]);
in_degree[x][y] --;
if (in_degree[x][y] == 0) q.emplace(x, y);
}
}
cout << *max_element(dp[n - 1].begin(), dp[n - 1].end()) << endl;
一般线性dp
包括 前缀dp 和 01dp
常见思路
Tip
dp[i]: 以第i个元素作为结尾的最大值/最小值
比较高级一点的技巧
- 以结果做状态
背包dp
01 背包
心路历程
dp 的做题步骤：
- 划分阶段 以容量为阶段
- 定义状态 f(i) = 容量为i的背包所能达到的最大价值
- 状态转移 f(i) = max(f(i), f(i - v) + w)
但这样每个状态都能选择任意物品进行转移，而非每个物品选择一次
换一种思路
- 划分阶段 用01dp的思路 以物品划分阶段
- 定义状态 f(i) = 前i个物品所能达到的最大价值
无法转移，扩充一维
- 定义状态 f(i) = 前i个物品，容量为j的背包所能达到的最大价值
- 状态转移 如果不选，直接从前i-1个物品的状态继承；如果选f(i,j)从f(i-1, j-v)加上w转