C++动态规划：从暴力搜索到最优解

第二章：DP 的三大特征——识别 DP 问题的火眼金睛

2.1 特征一：最优子结构（Optimal Substructure）

一个大问题的最优解包含其子问题的最优解。就像搭积木，整体的最优结构由局部的最优结构组成。

经典例子：最短路径问题
如果从 A 到 C 的最短路径经过 B，那么 A 到 B 和 B 到 C 的路径也必定是最短的。

// 伪代码示意
最短路径(A, C) = 最短路径(A, B) + 最短路径(B, C)

2.2 特征二：重叠子问题（Overlapping Subproblems）

不同的大问题会共享相同的小问题。这是我们能'记忆化'的基础。

// 斐波那契中明显存在重叠
fib(5) 需要 fib(3)
fib(4) 也需要 fib(3) // 重叠！

2.3 特征三：无后效性（No Aftereffect）

当前状态一旦确定，后续决策不受之前决策影响。这是 DP 能够顺序计算的关键。

想象你在玩迷宫游戏：你当前的位置决定了下一步的选择，但不需要知道你是怎么走到这里的。

第三章：DP 的两种实现方式——自顶向下与自底向上

3.1 方法一：记忆化搜索（Memoization，自顶向下）

在递归基础上加一张'备忘录'。

#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);
}

优点：

• 思维自然，接近问题原始定义
• 只计算需要的子问题

缺点：

• 递归有栈溢出风险
• 常数开销较大

3.2 方法二：递推（Tabulation，自底向上）

从小问题开始，逐步构建到大问题。

// 方法 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 问题分类详解——六大经典模型

4.1 模型一：线性 DP

例题 1：最长递增子序列（LIS）

问题：找出序列中最长的严格递增子序列的长度。

状态定义：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();
}

4.2 模型二：背包 DP

例题 2：0-1 背包问题

问题：有 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;
}

背包问题变种对比表：

4.3 模型三：区间 DP

例题 3：石子合并问题

问题：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;
}

4.4 模型四：状态压缩 DP

例题 4：旅行商问题（TSP）简化版

问题：访问 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;
}

4.5 模型五：树形 DP

例题 5：二叉树中的最大路径和

问题：在二叉树中找一条路径（节点序列），使得路径上节点值之和最大。

状态定义：

• 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;
}

4.6 模型六：数位 DP

例题 6：计算 1 到 n 中数字 x 出现的次数

问题：计算在 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;
}

第五章：DP 优化技巧——让算法飞起来

5.1 空间优化：滚动数组

当状态转移只依赖前几个状态时，可以压缩空间。

// 斐波那契的空间优化
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;
}

5.2 时间优化：斜率优化与四边形不等式

对于形如 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;
}

5.3 状态压缩优化：位运算技巧

// 常用位运算操作
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 实战策略——解决陌生问题的通用方法

6.1 五步解题法

面对陌生 DP 问题时，按照以下步骤思考：

1. 问题分析：判断是否具有最优子结构和重叠子问题
2. 状态定义：dp[...] 表示什么？状态参数需要哪些？
3. 状态转移：如何从已知状态推出新状态？
4. 边界条件：最小子问题的答案是什么？
5. 计算顺序：应该按什么顺序计算状态？

6.2 调试技巧

// 添加调试输出的 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;
}

6.3 常见错误与陷阱

1. 数组越界：转移时注意索引范围
2. 初始化错误：边界条件设置不当
3. 状态转移遗漏：没有考虑所有可能情况
4. 循环顺序错误：某些 DP 需要特定计算顺序
5. 整数溢出：使用 long long 或取模

第七章：从 DP 到人生——思维方式的升华

7.1 DP 思维的三个层次

1. 第一层：暴力搜索——看到问题直接尝试所有可能
2. 第二层：记忆化搜索——发现重复计算，开始记录答案
3. 第三层：动态规划——系统性地自底向上构建解

7.2 生活中的 DP 思维

动态规划不仅是一种算法，更是一种解决问题的方法论：

1. 最优子结构：大目标分解为小目标，每个阶段都做出最优选择
2. 状态定义：明确当前所处的位置和条件
3. 状态转移：知道如何从现在状态过渡到下一状态
4. 边界条件：清楚起点在哪里
5. 无后效性：过去的决定不影响未来的选择，着眼当下

7.3 给学习者的终极建议

1. 从简单开始：先掌握线性 DP、背包 DP 等基础模型
2. 多画图：在纸上画出状态转移图，直观理解
3. 刻意练习：每个类型刷 10-20 道经典题目
4. 总结归纳：建立自己的 DP 问题分类体系
5. 融会贯通：看到问题先想'这能不能用 DP 解？'

结语：DP 之美——复杂世界的简单规律

动态规划的美丽之处在于，它揭示了复杂问题背后的简单结构。无论是斐波那契数列、最短路径还是旅行商问题，表面上千差万别，但核心都是：通过保存子问题的解，避免重复计算，最终得到整体最优解。

学习 DP 的过程就像学习下棋：开始时只能看到眼前一步（暴力搜索），后来能看到两三步（记忆化搜索），最终能推演整个棋局（动态规划）。这种思维方式一旦掌握，不仅让你成为更好的程序员，更让你成为更优秀的思考者。

记住贝尔曼的名言："动态规划是一种将复杂问题分解为更简单子问题的方法，通过解决每个子问题一次并将答案存储起来，避免重复解决相同的子问题。"

在算法世界中，动态规划是王冠上的明珠；在人生旅途中，它是指引方向的智慧之光。 开始你的 DP 之旅吧，从第一个 dp[0] = 1 开始，一步步构建属于你的最优解。