动态规划实战教程（C++）—— 从入门到进阶的 6 道算法题模板

从状态定义、转移方程到空间优化，结合爬楼梯、01背包、最长公共子序列、区间DP与状态压缩，系统掌握动态规划解题套路（C++版）

发表于 2026/02/28

作者 xirain

13 分钟阅读

动态规划（DP）常被说成“算法面试分水岭”：会的人觉得是模板题，不会的人感觉每题都像新题。

这篇文章给你一个由浅入深、可直接套用的 C++ 实战路线：

先掌握统一的 DP 思考框架（状态、转移、初始化、遍历顺序）
再做 6 道经典题，覆盖线性 DP、背包、序列 DP、区间 DP、状态压缩 DP
每题都给出可运行 C++ 代码 + 复杂度 + 常见坑

📌 建议阅读顺序：练习 1 → 2 → 3 → 4 → 5 → 6。前 4 题是高频面试核心，后 2 题拉开难度。

先建立一个通用解题框架

无论题目看起来多花哨，都先回答下面 5 个问题：

状态是什么？ dp[i] / dp[i][j] 表示什么含义？
转移从哪里来？ 当前状态由哪些更小子问题转移？
初始条件是什么？ 第一个状态如何成立？
遍历顺序怎么定？ 先算谁，后算谁？
答案在哪里？ dp[n] 还是 max(dp[...])？

你可以把它当作面试口述模板：

“我先定义状态，再写转移，再补初始化，最后确认遍历顺序和答案位置。”

练习 1：爬楼梯（线性 DP 入门）

题目：每次可以爬 1 或 2 阶，问到第 n 阶有多少种方法。

思路

状态：dp[i] = 到达第 i 阶的方法数
转移：dp[i] = dp[i-1] + dp[i-2]
初始化：dp[0]=1（站在地面算 1 种），dp[1]=1

  
#include <iostream>
#include <vector>
using namespace std;

int climbStairs(int n) {
    if (n <= 1) return 1;
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    cout << climbStairs(5) << "\n"; // 8
}

复杂度：时间 O(n)，空间 O(n)。

空间优化（滚动变量）

只依赖前两个状态，可以降到 O(1)：

  
int climbStairsOptimized(int n) {
    if (n <= 1) return 1;
    int a = 1, b = 1; // a=dp[i-2], b=dp[i-1]
    for (int i = 2; i <= n; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

练习 2：打家劫舍（线性 DP 进阶）

题目：数组 nums 表示每间房的钱，不能偷相邻房子，求最大金额。

思路

状态：dp[i] = 偷到下标 i 时的最大收益（考虑 0..i）
选择：
- 不偷 i：dp[i-1]
- 偷 i：dp[i-2] + nums[i]
转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int rob(const vector<int>& nums) {
    int n = (int)nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    vector<int> dp(n, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < n; ++i) {
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
}

int main() {
    vector<int> nums{2, 7, 9, 3, 1};
    cout << rob(nums) << "\n"; // 12
}

常见坑：

边界 n=0/1/2 容易漏
dp[i] 的语义要固定，否则转移会乱

练习 3：01 背包（经典二维 DP）

题目：有 n 件物品，每件有重量 w[i] 和价值 v[i]，背包容量 W，每件最多选一次。

二维写法（先理解）

状态：dp[i][j] = 只看前 i 件物品、容量为 j 的最大价值
转移：
- 不选第 i 件：dp[i-1][j]
- 选第 i 件：dp[i-1][j-w[i]] + v[i]（前提 j>=w[i]）

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapsack2D(const vector<int>& w, const vector<int>& v, int W) {
    int n = (int)w.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= W; ++j) {
            dp[i][j] = dp[i - 1][j];
            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][W];
}

int main() {
    vector<int> w{1, 3, 4};
    vector<int> v{15, 20, 30};
    cout << knapsack2D(w, v, 4) << "\n"; // 35
}

一维优化（面试更常问）

  
int knapsack1D(const vector<int>& w, const vector<int>& v, int W) {
    int n = (int)w.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; ++i) {
        // 关键：01背包必须倒序遍历容量，避免同一物品重复使用
        for (int j = W; j >= w[i]; --j) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

关键记忆点：

01 背包倒序
完全背包正序（每件可重复选）

练习 4：最长公共子序列 LCS（序列 DP）

题目：给定字符串 a、b，求最长公共子序列长度。

思路

状态：dp[i][j] = a 前 i 个字符和 b 前 j 个字符的 LCS 长度
转移：
- 若 a[i-1] == b[j-1]：dp[i][j] = dp[i-1][j-1] + 1
- 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

  
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int lcs(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}

int main() {
    cout << lcs("abcde", "ace") << "\n"; // 3
}

复杂度：时间 O(n*m)，空间 O(n*m)。

练习 5：戳气球（区间 DP）

题目：数组 nums，每次戳破一个气球 k，得分是 nums[left] * nums[k] * nums[right]，求最大总分。

这题难点在于：最后戳哪个气球比“先戳哪个”更好建模。

思路（区间 DP 标准套路）

在两侧补 1，得到 arr
状态：dp[l][r] = 开区间 (l, r) 内全部戳完的最大得分
枚举最后一个戳的 k： dp[l][r] = max(dp[l][k] + dp[k][r] + arr[l]*arr[k]*arr[r])

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxCoins(vector<int> nums) {
    int n = (int)nums.size();
    vector<int> arr(n + 2, 1);
    for (int i = 0; i < n; ++i) arr[i + 1] = nums[i];

    int N = n + 2;
    vector<vector<int>> dp(N, vector<int>(N, 0));

    // 按区间长度从小到大
    for (int len = 2; len < N; ++len) {
        for (int l = 0; l + len < N; ++l) {
            int r = l + len;
            for (int k = l + 1; k < r; ++k) {
                dp[l][r] = max(dp[l][r],
                               dp[l][k] + dp[k][r] + arr[l] * arr[k] * arr[r]);
            }
        }
    }
    return dp[0][N - 1];
}

int main() {
    cout << maxCoins({3, 1, 5, 8}) << "\n"; // 167
}

区间 DP 两个固定问题：

区间表示是 [l, r] 还是 (l, r)？
外层循环按什么顺序？（通常是按区间长度）

练习 6：旅行商问题 TSP（状态压缩 DP）

题目：从城市 0 出发，访问所有城市一次并回到 0，求最短路径。

思路

状态：dp[mask][u] = 从 0 出发，访问集合 mask，最后停在 u 的最短路
转移：从上一个城市 v 转移到 u
mask 用二进制表示“访问了哪些城市”

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int tsp(const vector<vector<int>>& dist) {
    const int INF = 1e9;
    int n = (int)dist.size();
    int S = 1 << n;

    vector<vector<int>> dp(S, vector<int>(n, INF));
    dp[1][0] = 0; // 只访问0号点，停在0号点

    for (int mask = 1; mask < S; ++mask) {
        for (int u = 0; u < n; ++u) {
            if (!(mask & (1 << u))) continue;
            if (dp[mask][u] == INF) continue;

            for (int v = 0; v < n; ++v) {
                if (mask & (1 << v)) continue;
                int nextMask = mask | (1 << v);
                dp[nextMask][v] = min(dp[nextMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }

    int full = S - 1;
    int ans = INF;
    for (int u = 0; u < n; ++u) {
        ans = min(ans, dp[full][u] + dist[u][0]);
    }
    return ans;
}

int main() {
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    cout << tsp(dist) << "\n"; // 80
}

复杂度：O(n^2 * 2^n)，适合 n <= 20 左右。

一张表总结常见 DP 类型

类型	常见状态	典型题	关键点
线性 DP	`dp[i]`	爬楼梯、打家劫舍	通常只依赖前几个状态，可滚动优化
背包 DP	`dp[i][j]` 或 `dp[j]`	01背包、完全背包	01倒序、完全正序
序列 DP	`dp[i][j]`	LCS、编辑距离	二维含义必须先讲清楚
区间 DP	`dp[l][r]`	戳气球、石子合并	按区间长度递推
状压 DP	`dp[mask][i]`	TSP、最短哈密顿路	`mask` 含义 + 位运算熟练

面试实战建议：如何 10 分钟写出 DP

先说状态定义，不急着写代码：多数错误都死在“定义不清”。
写出 1~2 个小样例手推：验证转移是否自洽。
先写朴素二维，再做优化：不要一上来就滚动数组。
边界单独处理：n=0、n=1、空字符串、容量为 0。
记住两个高频遍历顺序：
- 01 背包：容量倒序
- 区间 DP：区间长度从短到长

结语

动态规划并不是“灵感题”，而是“建模题”。

当你能稳定回答“状态是什么、怎么转移、顺序为何正确”时，DP 就从玄学变成了模板化工程能力。建议你把本文 6 题全部亲手敲一遍，再找 10 道同类型题做迁移练习，提升会非常明显。

如果你愿意，我可以继续写下一篇：《动态规划专项刷题清单（30 题，按难度分层，附 C++ 题解模板）》。

数据结构

c++ 动态规划算法教程背包问题 LCS 区间DP 状态压缩

本文由作者按照 CC BY 4.0 进行授权