C++算法
C++动态规划：从暴力搜索到最优解
C++ 动态规划的核心概念、三大特征及两种实现方式（记忆化搜索与递推）。涵盖了线性 DP、背包 DP、区间 DP、状态压缩 DP、树形 DP 和数位 DP 六大经典模型，并提供了最长递增子序列、0-1 背包、石子合并等例题的代码实现。此外还讲解了空间优化、斜率优化等技巧以及五步解题法，帮助读者掌握从暴力搜索到最优解的算法思维。
C++ 动态规划的核心概念、三大特征及两种实现方式（记忆化搜索与递推）。涵盖了线性 DP、背包 DP、区间 DP、状态压缩 DP、树形 DP 和数位 DP 六大经典模型，并提供了最长递增子序列、0-1 背包、石子合并等例题的代码实现。此外还讲解了空间优化、斜率优化等技巧以及五步解题法，帮助读者掌握从暴力搜索到最优解的算法思维。
让我们从一个经典的故事开始。1202 年，意大利数学家斐波那契提出了著名的兔子问题，由此诞生了斐波那契数列。800 年后，当我们在计算机上计算这个数列时，却遇到了麻烦。
// 最直观的递归解法
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
看起来很美，对吧？但当我尝试计算 fib(50) 时，计算机开始发出痛苦的呻吟。让我们看看发生了什么：
fib(5) = fib(4) + fib(3) = (fib(3) + fib(2)) + (fib(2) + fib(1)) = ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) = ...
惊人的事实：计算 fib(5) 需要调用函数 15 次，而 fib(50) 需要约 400 亿次调用！为什么？因为我们在重复计算相同的东西：fib(3) 被计算了 2 次，fib(2) 被计算了 3 次...
动态规划（Dynamic Programming）的思想很简单却深刻：如果一个问题可以分解为重叠的子问题，那就记住每个子问题的解，避免重复计算。
1950 年代，理查德·贝尔曼在兰德公司研究多阶段决策过程时，创造了'动态规划'这个术语。他后来说："'动态'是因为时间是重要的组成部分，'规划'是因为我们在优化一个计划。"
一个大问题的最优解包含其子问题的最优解。就像搭积木，整体的最优结构由局部的最优结构组成。
经典例子：最短路径问题
如果从 A 到 C 的最短路径经过 B，那么 A 到 B 和 B 到 C 的路径也必定是最短的。
// 伪代码示意
最短路径(A, C) = 最短路径(A, B) + 最短路径(B, C)
不同的大问题会共享相同的小问题。这是我们能'记忆化'的基础。
// 斐波那契中明显存在重叠
fib(5) 需要 fib(3)
fib(4) 也需要 fib(3) // 重叠！
当前状态一旦确定，后续决策不受之前决策影响。这是 DP 能够顺序计算的关键。
想象你在玩迷宫游戏：你当前的位置决定了下一步的选择，但不需要知道你是怎么走到这里的。
在递归基础上加一张'备忘录'。
#include <iostream>
#include <vector>
using namespace std;
// 方法 1：记忆化搜索
int fib_memo(int n, vector<int>& memo) {
if (n <= 1) return n;
// 如果已经计算过，直接返回
if (memo[n] != -1) {
return memo[n];
}
// 计算并存储
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo);
return memo[n];
}
int fib_memoization(int n) {
vector<int> memo(n + 1, -1); // 备忘录初始化为 -1
return fib_memo(n, memo);
}
优点：
缺点：
从小问题开始，逐步构建到大问题。
// 方法 2：递推（动态规划表）
int fib_tabulation(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1, 0);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
空间优化版本：
int fib_optimized(int n) {
if (n <= 1) return n;
int prev2 = 0; // f(i-2)
int prev1 = 1; // f(i-1)
int current; // f(i)
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
优点：
缺点：
问题：找出序列中最长的严格递增子序列的长度。
状态定义：dp[i] = 以 nums[i] 结尾的最长递增子序列长度
状态转移：dp[i] = max(dp[j]) + 1，对所有 j < i 且 nums[j] < nums[i]
完整代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
vector<int> dp(n, 1); // 每个元素自身就是长度为 1 的 LIS
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
// 优化版本：O(n log n) 使用二分查找
int lengthOfLIS_optimized(vector<int>& nums) {
vector<int> tails; // tails[k] 存储长度为 k+1 的 LIS 的最小末尾值
for (int num : nums) {
// 在 tails 中二分查找第一个≥num 的位置
auto it = lower_bound(tails.begin(), tails.end(), num);
if (it == tails.end()) {
tails.push_back(num); // 所有末尾都小于 num，可以延长 LIS
} else {
*it = num; // 更新该长度的最小末尾值
}
}
return tails.size();
}
问题：有 n 件物品，第 i 件物品重量 w[i]，价值 v[i]，背包容量 C。每件物品只能选 0 或 1 次，求最大价值。
状态定义：dp[i][j] = 前 i 件物品放入容量为 j 的背包的最大价值
状态转移：
dp[i][j] = max(
dp[i-1][j], // 不选第 i 件
dp[i-1][j-w[i]] + v[i] // 选第 i 件 (如果 j ≥ w[i])
)
完整代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 二维 DP 版本
int knapsack_2D(int C, vector<int>& w, vector<int>& v) {
int n = w.size();
vector<vector<int>> dp(n + 1, vector<int>(C + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
// 不选第 i 件物品
dp[i][j] = dp[i-1][j];
// 如果能选第 i 件物品，考虑选择它
if (j >= w[i-1]) {
dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]);
}
}
}
return dp[n][C];
}
// 一维优化版本（空间复杂度 O(C)）
int knapsack_1D(int C, vector<int>& w, vector<int>& v) {
int n = w.size();
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; i++) {
// 必须从后往前遍历，避免同一物品被重复选择
for (int j = C; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
return dp[C];
}
int main() {
vector<int> weights = {2, 3, 4, 5};
vector<int> values = {3, 4, 5, 6};
int capacity = 8;
cout << "最大价值 (2D): " << knapsack_2D(capacity, weights, values) << endl;
cout << "最大价值 (1D): " << knapsack_1D(capacity, weights, values) << endl;
// 输出：10 (选择物品 1,3,4)
return 0;
}
| 问题类型 | 特点 | 状态转移关键 |
|---|---|---|
| 0-1 背包 | 每件物品选 0 或 1 次 | 从后往前遍历 |
| 完全背包 | 每件物品无限次 | 从前往后遍历 |
| 多重背包 | 每件物品有限次 | 二进制拆分优化 |
| 分组背包 | 每组最多选一件 | 先遍历容量再遍历组内物品 |
问题：N 堆石子排成一排，每次合并相邻两堆，代价为两堆石子数之和，求合并成一堆的最小总代价。
状态定义：dp[i][j] = 合并第 i 到第 j 堆石子的最小代价
状态转移：
dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum[i][j]
其中 i ≤ k < j
sum[i][j] 是第 i 到第 j 堆石子总数
完整代码：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int stoneMerge(vector<int>& stones) {
int n = stones.size();
if (n == 0) return 0;
// 前缀和，方便计算 sum[i][j]
vector<int> prefix(n + 1, 0);
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i-1] + stones[i-1];
}
// dp[i][j] 表示合并 [i,j] 的最小代价
vector<vector<int>> dp(n, vector<int>(n, 0));
// 枚举区间长度
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
// 枚举分割点
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k+1][j] + (prefix[j+1] - prefix[i]);
dp[i][j] = min(dp[i][j], cost);
}
}
}
return dp[0][n-1];
}
int main() {
vector<int> stones = {4, 5, 9, 4};
cout << "最小合并代价：" << stoneMerge(stones) << endl;
// 输出：44
// 合并过程：(4 5) -> 9 (代价 9), (9 4) -> 13 (代价 13), (9 13) -> 22 (代价 22), 总代价 44
return 0;
}
问题：访问 n 个城市，每个城市恰好一次，最后回到起点，求最短路径。
状态定义：dp[mask][i] = 当前访问过的城市集合为 mask，最后在城市的 i 的最小路径长度
其中 mask 用二进制表示，第 k 位为 1 表示城市 k 已访问
状态转移：
dp[mask][i] = min(dp[prev_mask][j] + dist[j][i])
其中 prev_mask = mask ^ (1 << i)，即上一次没在城市 i
完整代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int tsp(vector<vector<int>>& dist) {
int n = dist.size();
if (n == 0) return 0;
// dp[mask][i]: 访问过的城市集合为 mask，现在在城市 i 的最小代价
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX / 2));
// 初始化：从城市 0 出发
dp[1][0] = 0; // 只访问了城市 0，现在在城市 0
// 遍历所有状态
for (int mask = 1; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
// 如果当前状态不可达，跳过
if (dp[mask][i] == INT_MAX / 2) continue;
// 尝试前往下一个城市 j
for (int j = 0; j < n; j++) {
// 如果 j 已经访问过，跳过
if (mask & (1 << j)) continue;
int new_mask = mask | (1 << j);
dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j]);
}
}
}
// 最后要回到起点城市 0
int ans = INT_MAX;
int full_mask = (1 << n) - 1;
for (int i = 1; i < n; i++) {
if (dp[full_mask][i] < INT_MAX / 2 && dist[i][0] < INT_MAX / 2) {
ans = min(ans, dp[full_mask][i] + dist[i][0]);
}
}
return ans;
}
int main() {
// 4 个城市的距离矩阵
vector<vector<int>> dist = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
cout << "最短哈密顿回路长度：" << tsp(dist) << endl;
// 输出：80 (0->1->3->2->0)
return 0;
}
问题：在二叉树中找一条路径（节点序列），使得路径上节点值之和最大。
状态定义：
max_gain(node)：以 node 为起点的向下路径的最大和max_sum 记录答案状态转移：
max_gain(node) = node->val + max(0, max_gain(left), max_gain(right))
max_sum = max(max_sum, node->val + max(0, max_gain(left)) + max(0, max_gain(right)))
完整代码：
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
private:
int maxSum;
int maxGain(TreeNode* node) {
if (!node) return 0;
// 递归计算左右子树的最大贡献值
int leftGain = max(maxGain(node->left), 0);
int rightGain = max(maxGain(node->right), 0);
// 当前节点的最大路径和（包含当前节点）
int priceNewpath = node->val + leftGain + rightGain;
// 更新全局最大和
maxSum = max(maxSum, priceNewpath);
// 返回当前节点的最大贡献值（只能选择一边）
return node->val + max(leftGain, rightGain);
}
public:
int maxPathSum(TreeNode* root) {
maxSum = INT_MIN;
maxGain(root);
return maxSum;
}
};
// 构建测试树
TreeNode* buildTestTree() {
/*
10
/ \
2 10
/ \ \
20 1 -25
/ \
3 4
*/
TreeNode* root = new TreeNode(10);
root->left = new TreeNode(2);
root->right = new TreeNode(10);
root->left->left = new TreeNode(20);
root->left->right = new TreeNode(1);
root->right->right = new TreeNode(-25);
root->right->right->left = new TreeNode(3);
root->right->right->right = new TreeNode(4);
return root;
}
int main() {
Solution solution;
TreeNode* root = buildTestTree();
cout << "二叉树最大路径和：" << solution.maxPathSum(root) << endl;
// 输出：42 (路径：20->2->10->10)
return 0;
}
问题：计算在 1 到 n 的所有整数中，数字 x（0-9）出现的次数。
状态定义：dp[pos][cnt][limit][lead]
pos: 当前处理到的位数（从高位到低位）cnt: 当前已统计到的数字 x 的出现次数limit: 是否受到 n 的限制（当前位能否取 9）lead: 是否有前导零完整代码：
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
class DigitDP {
private:
vector<int> digits; // 存储 n 的每一位
int dp[20][20][2][2]; // 记忆化数组
// pos: 当前处理的位置
// cnt: 当前统计到的数字 x 出现的次数
// limit: 是否受到 n 的限制
// lead: 是否有前导零
int dfs(int pos, int cnt, bool limit, bool lead, int x) {
// 递归边界：处理完所有位
if (pos == digits.size()) {
return cnt;
}
// 记忆化：如果已经计算过，直接返回
if (dp[pos][cnt][limit][lead] != -1) {
return dp[pos][cnt][limit][lead];
}
int ans = 0;
int up = limit ? digits[pos] : 9; // 当前位的上界
for (int d = 0; d <= up; d++) {
// 新的 limit 值：如果之前 limit 为真且当前位等于上界，则继续 limit
bool new_limit = limit && (d == up);
// 新的 lead 值：如果之前有前导零且当前位为 0，则继续有前导零
bool new_lead = lead && (d == 0);
// 新的 cnt 值
int new_cnt = cnt;
if (!new_lead || d != 0) {
// 如果不是前导零
if (d == x) {
new_cnt++;
}
}
ans += dfs(pos + 1, new_cnt, new_limit, new_lead, x);
}
return dp[pos][cnt][limit][lead] = ans;
}
public:
int countDigitX(int n, int x) {
if (n <= 0) return 0;
// 将 n 分解为各位数字
digits.clear();
while (n > 0) {
digits.push_back(n % 10);
n /= 10;
}
reverse(digits.begin(), digits.end()); // 反转，使高位在前
// 初始化记忆化数组
memset(dp, -1, sizeof(dp));
return dfs(0, 0, true, true, x);
}
};
int main() {
DigitDP digitDP;
int n = 12345;
int x = 2;
cout << "在 1 到" << n << "中，数字" << x << "出现了" << digitDP.countDigitX(n, x) << "次" << endl;
// 输出：在 1 到 12345 中，数字 2 出现了 2849 次
return 0;
}
当状态转移只依赖前几个状态时，可以压缩空间。
// 斐波那契的空间优化
int fib_space_optimized(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
对于形如 dp[i] = min(dp[j] + cost(j, i)) 的转移，可以使用单调队列优化。
// 单调队列优化 DP 示例：滑动窗口最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (nums.empty()) return {};
deque<int> dq; // 存储下标，保证队列中元素对应值递减
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
// 移除窗口外的元素
if (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// 移除小于当前元素的队尾元素
while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
dq.push_back(i);
// 当窗口形成时记录最大值
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
// 常用位运算操作
int setBit(int mask, int pos) {
return mask | (1 << pos); // 设置第 pos 位为 1
}
int clearBit(int mask, int pos) {
return mask & ~(1 << pos); // 设置第 pos 位为 0
}
bool isSet(int mask, int pos) {
return (mask >> pos) & 1; // 检查第 pos 位是否为 1
}
int toggleBit(int mask, int pos) {
return mask ^ (1 << pos); // 翻转第 pos 位
}
// 遍历 mask 的所有子集（重要技巧！）
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
// 处理子集 sub
}
面对陌生 DP 问题时，按照以下步骤思考：
dp[...] 表示什么？状态参数需要哪些？// 添加调试输出的 DP 函数
void debugDP(vector<vector<int>>& dp) {
cout << "DP 表内容:" << endl;
for (int i = 0; i < dp.size(); i++) {
cout << "第" << i << "行: ";
for (int j = 0; j < dp[i].size(); j++) {
cout << dp[i][j] << " ";
}
cout << endl;
}
}
// 验证边界条件
bool checkBoundary(int n, int m) {
if (n < 0 || m < 0) {
cout << "错误：访问了负索引" << endl;
return false;
}
return true;
}
long long 或取模动态规划不仅是一种算法，更是一种解决问题的方法论：
动态规划的美丽之处在于，它揭示了复杂问题背后的简单结构。无论是斐波那契数列、最短路径还是旅行商问题，表面上千差万别，但核心都是：通过保存子问题的解，避免重复计算，最终得到整体最优解。
学习 DP 的过程就像学习下棋：开始时只能看到眼前一步（暴力搜索），后来能看到两三步（记忆化搜索），最终能推演整个棋局（动态规划）。这种思维方式一旦掌握，不仅让你成为更好的程序员，更让你成为更优秀的思考者。
记住贝尔曼的名言："动态规划是一种将复杂问题分解为更简单子问题的方法，通过解决每个子问题一次并将答案存储起来，避免重复解决相同的子问题。"
在算法世界中，动态规划是王冠上的明珠；在人生旅途中，它是指引方向的智慧之光。 开始你的 DP 之旅吧，从第一个 dp[0] = 1 开始，一步步构建属于你的最优解。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online