当前位置：首页 > ds >正文

动态规划3、悟到核心

ds 2025/9/6 6:10:56

题目引入：

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cstring>
using namespace std;// dp[i]考虑前i家店能收获的最大价值
// 面对第i家店铺，你可以选择偷，或者不偷
// 偷的话，i-1家就不能偷int main() {int N;cin >> N;vector<int> V(N + 1);for (int i = 1; i <= N; i++) {cin >> V[i];}if (N == 0) {cout << 0 << endl;return 0;}if (N == 1) {cout << V[1] << endl;return 0;}vector<int> dp(N + 1);dp[1] = V[1];dp[2] = max(V[1], V[2]);for (int i = 3; i <= N; i++) {dp[i] = max(dp[i - 1], dp[i - 2] + V[i]);}cout << dp[N] << endl;return 0;
}

dp的核心：

用子问题的最优解来构建原问题的最优解

1. 最优子结构

这是dp的”根基“

——大问题的最优解，一定可以由子问题的最优解提出

比如：前i家店的最大价值，只跟前i-1和i-2家的最大价值有关

2. 状态设计

这是dp的“语言”

——我该怎么用“状态”表示我解决问题的中间结果？

dp[i]表示“处理到第i家店时的最大价值‘

dp[x][y][fuel]表示走到xy位置，持有fuel汽油时的最小花费

3. 状态转移方程

这是dp的”灵魂表达式“

——状态A是怎么从状态B、C、D...推出来的？

4. 记忆化

记忆化搜索、自底向上的dp表格...

——已经知道结果了，就别再重新算一遍！

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cstring>
using namespace std;// 甚，原来是区间dp啊！
int dp[11][11];
bool vis[11][11];string A, B;
int n;int dfs(int l, int r) {if (l > r) return 0;if (vis[l][r]) return dp[1][r]; // 剪枝处理vis[l][r] = true;int i = n - (r - l + 1);int take_left = (int)A[l] * (int)B[i] + dfs(l + 1, r);int take_right = (int)A[r] * (int)B[i] + dfs(l, r - 1);return dp[l][r] = max(take_left, take_right);
}int main() {while (cin >> A >> B) {n = A.size();memset(dp, 0, sizeof(dp));memset(vis, 0, sizeof(vis));cout << dfs(0, n - 1) << endl;}return 0;
}

直接暴力dfs，字符数量少

但是如果字符数量大的话我们就要建dp表格了！

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cstring>
using namespace std;// 本题的状态为：dp[l][r] = 从 A[l..r] 与 B 匹配能得到的最大能量int main() {string A, B;while (cin >> A >> B) {int n = A.size();vector<vector<int>> dp(n, vector<int>(n, 0));// 区间长度for (int len = 1; len <= n; len++) {for (int l = 0; l + len <= n; l++) {int r = l + len - 1;int i = n - (r - l + 1);if (l == r) {dp[l][r] = A[l] * B[i];}else {dp[l][r] = max(A[l] * B[i] + dp[l + 1][r],A[r] * B[i] + dp[l][r - 1]);}}}cout << dp[0][n - 1] << endl;}return 0;
}

几乎所有 DP 题目，一开始都可以用 DFS 去建模，而动态规划只是对 DFS 的一种优化，优化掉了“重复子问题”的计算。

🍃第一步：DFS 是怎么来的？

很多问题，我们一开始会有一种“我从起点一路走到底”的直觉，这就很像 DFS —— 沿着一个路径一直走下去。

举个例子：

比如之前那个盗贼问题（不能偷相邻的店）：

我们可以这样思考：

我现在站在第 i 家店门口，我可以选择“偷”或者“不偷”。

那我们就写一个函数：

int dfs(int i) { if (i <= 0) return 0; return max(dfs(i - 1), dfs(i - 2) + V[i]); // 不偷 or 偷 }

你看，这就是标准的 DFS：尝试所有选择。

🌱第二步：DFS 有什么缺点？

它的最大问题就是：

会重复算很多次！！！

比如你在求 dfs(10) 的时候，它会递归去算 dfs(9) 和 dfs(8)，但 dfs(9) 又会去算 dfs(8) 和 dfs(7)，你看：

dfs(8) 被重复算了两次
dfs(7) 被重复算了三次
dfs(6) 被重复算了五次……🌪️

这样效率就很差！

🌟第三步：怎么办？优化它！

于是我们就说：

我干嘛重复算呀！我算过的结果，记下来不就行了吗！

这就有了“记忆化搜索”：

int memo[10001]; // 初始化为 -1 int dfs(int i) { if (i <= 0) return 0; if (memo[i] != -1) return memo[i]; return memo[i] = max(dfs(i - 1), dfs(i - 2) + V[i]); }

这样我们就把DFS + 记忆化结合起来了。

而这个做法，其实就是“动态规划的雏形”。