动态规划 DP：原理、图解与 C++ 实战

一、什么是动态规划

动态规划（Dynamic Programming，DP）是一种把复杂问题拆成重叠子问题来求解的算法思想。它通过记录每个子问题的答案，避免在递归求解时重复计算，从而把指数级复杂度压到多项式级。

它的核心思想可以用三个关键词概括：

• 最优子结构：大问题的最优解能由子问题的最优解构造出来
• 重叠子问题：递归求解时同一子问题会被反复计算
• 无后效性：当前状态只依赖之前的状态，不依赖之后怎么走

1.1 DP 与其他算法的对比

二、核心原理与图解

掌握 DP 的关键是抓住"三要素：状态、转移、边界"。把这三件事想清楚，代码就自然写出来了。

2.1 DP 三要素图解

2.2 自底向上填表过程

DP 最常见的实现方式是自底向上（Bottom-Up）——从最小的子问题开始，按顺序填一张 DP 表，每次填一个格子时它依赖的格子已经填好了。以爬楼梯为例：

2.3 与记忆化搜索的对比

DP 还有另一种实现：自顶向下记忆化搜索（Top-Down with Memoization）。从大问题出发递归，遇到子问题时先查表，没算过才递归。两种实现等价但风格不同：

2.4 复杂度分析

三、通用模板

下面给出两种最常见的 DP 模板框架——一维 DP 和二维 DP，分别覆盖 80% 的题目。

3.1 一维 DP 模板

// 一维 DP 通用模板：状态只依赖前几个状态
int solve(int n) {
    if (n <= 1) return n;  // 特判小数据

    vector<int> dp(n + 1);  // dp[i] 表示第 i 个状态的答案
    // ① 边界条件
    dp[0] = 0;
    dp[1] = 1;

    // ② 按顺序填表，写出转移方程
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2];  // 例：斐波那契式转移
    }
    return dp[n];
}

// 空间优化版：只用两个变量，O(1) 空间
int solveOpt(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

3.2 二维 DP 模板

// 二维 DP 通用模板：dp[i][j] 依赖 dp[i-1][j], dp[i][j-1] 等
int solve2D(const string& s1, const string& s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // ① 边界：空串情况
    for (int i = 0; i <= m; ++i) dp[i][0] = i;  // 例：编辑距离
    for (int j = 0; j <= n; ++j) dp[0][j] = j;

    // ② 双重循环填表
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];  // 字符相同，无需操作
            } else {
                dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
            }
        }
    }
    return dp[m][n];
}

四、示例一：爬楼梯

题目（LeetCode 70）：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法爬到楼顶？

4.1 思路：斐波那契式递推

到达第 n 阶有两种方式：从第 n-1 阶跨 1 步，或从第 n-2 阶跨 2 步。所以方法数 = 两者之和，这正是斐波那契数列的定义。

4.2 C++ 代码

// LeetCode 70：爬楼梯
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;  // 1 阶 1 种，2 阶 2 种

        // 状态：dp[i] = 爬到第 i 阶的方法数
        // 转移：dp[i] = dp[i-1] + dp[i-2]
        // 边界：dp[1]=1, dp[2]=2
        int prev2 = 1, prev1 = 2;  // dp[1], dp[2]

        for (int i = 3; i <= n; ++i) {
            int cur = prev1 + prev2;  // 当前 = 上一步 + 上上步
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

五、示例二：最长公共子序列 LCS

题目（LeetCode 1143）：给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。如果不存在公共子序列，返回 0。

5.1 思路：二维 DP

定义 dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度。两种情况：

• 若 text1[i-1] == text2[j-1]：这一对字符相同，必然可以加入子序列末尾，dp[i][j] = dp[i-1][j-1] + 1
• 否则：这一对字符至少有一个不选，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

5.2 C++ 代码

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

int longestCommonSubsequence(const string& text1, const string& text2) {
    int m = text1.size(), n = text2.size();
    // 状态：dp[i][j] = text1[0..i-1] 与 text2[0..j-1] 的 LCS 长度
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 边界：dp[0][j] = dp[i][0] = 0（空串与任意串 LCS 为 0）
    // 已在初始化时填好

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (text1[i-1] == text2[j-1]) {
                // 当前字符相同，加入 LCS 末尾
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                // 不同：跳过 text1 的当前字符或 text2 的当前字符
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

六、示例三：0-1 背包问题

题目：有 n 个物品和一个容量为 W 的背包。第 i 个物品的重量为 weight[i]，价值为 value[i]。每个物品只能选一次（要么拿要么不拿）。求在不超过容量的前提下能获得的最大价值。

6.1 思路：经典二维 DP

定义 dp[i][w] 表示从前 i 个物品中选，总重量不超过 w 时的最大价值。对第 i 个物品，有两种选择：

• 不拿：dp[i][w] = dp[i-1][w]（继承上一轮）
• 拿（仅当 weight[i-1] <= w）：dp[i][w] = dp[i-1][w - weight[i-1]] + value[i-1]

取两者较大值。

6.2 C++ 代码

#include <vector>
using namespace std;

// 0-1 背包：二维 DP 版本
int knapsack(const vector<int>& weight,
                const vector<int>& value,
                int W) {
    int n = weight.size();
    // 状态：dp[i][w] = 从前 i 个物品中选，总重 ≤ w 的最大价值
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    // 边界：dp[0][w] = 0, dp[i][0] = 0 已由初始化完成
    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            // 不拿第 i 个物品（下标 i-1）
            dp[i][w] = dp[i-1][w];
            // 拿（前提：装得下）
            if (w >= weight[i-1]) {
                int take = dp[i-1][w - weight[i-1]] + value[i-1];
                dp[i][w] = max(dp[i][w], take);
            }
        }
    }
    return dp[n][W];
}

// 空间优化：一维 DP，从右往左填表避免覆盖
int knapsackOpt(const vector<int>& weight,
                  const vector<int>& value,
                  int W) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);  // 只保留"容量"维度

    for (int i = 0; i < n; ++i) {
        // 关键：w 必须从大到小！否则 dp[w-wi] 会被本物品的更新覆盖
        for (int w = W; w >= weight[i]; --w) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

七、总结与适用场景

典型题目清单

• LeetCode 70：爬楼梯（线性 DP 入门）
• LeetCode 198：打家劫舍（线性 DP + 状态机）
• LeetCode 1143：最长公共子序列（二维 DP）
• LeetCode 72：编辑距离（二维 DP 经典）
• LeetCode 5：最长回文子串（区间 DP）
• LeetCode 322：零钱兑换（完全背包）
• LeetCode 416：分割等和子集（0-1 背包变体）
• LeetCode 198：树形 DP（打家劫舍 III）