很多「求最优」「求方案数」「能否达成」的问题，暴力枚举会指数爆炸，而动态规划把重叠子问题折叠成一张表，用多项式时间给出答案。
本文从「何时用 DP」出发，讲清状态、转移、边界、计算顺序，再用几道经典 LeetCode 风格的题目，给出可直接套用的 C++ 模板（自顶向下记忆化 + 自底向上递推）。

---

1. 什么时候想到动态规划？

先问自己三个问题：

1. 问题能否拆成子问题？ 大问题的最优（或计数）能否由「更小规模」的同类型问题组合得到。
2. 子问题是否大量重复？ 如果用朴素递归，同一状态会被算很多遍 —— 这正是 DP 要消除的浪费。
3. 是否具有最优子结构 / 无后效性？ 一旦确定了某个子问题的答案，后面决策不应再依赖「如何走到这个子问题」的细节路径（只依赖状态本身）。

若以上都成立，就可以尝试设计 状态 与 转移方程，用 记忆化 或 递推表 实现。

可以把 DP 理解成：带缓存的递归，或等价地，按拓扑序填表。

---

2. DP 四件套：状态、转移、初值、答案

要素	含义
状态	用少量变量概括「当前局面」—— 通常是下标、容量、是否选取等。
转移	dp[状态] = f(更小状态的 dp 值)，写出递推式。
初值（边界）	最小规模子问题的已知答案，用于启动递推。
目标	题目要的答案对应表中哪个格子（或如何从表上读出）。

实现上有两条路：

• 自顶向下（Top-down）：递归 + memo（unordered_map 或 vector 配合特殊值表示未计算）。
• 自底向上（Bottom-up）：显式循环填 dp 数组，常数因子更好、无递归栈风险。

下面模板二选一即可，很多题两种都能写。

---

3. 模板一：记忆化搜索（Top-down）

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

// 例：假设状态是一维下标 i，返回值是 int
int solve_memo(const vector<int>& a) {
    const int n = (int)a.size();
    vector<int> memo(n, INT_MIN);  // 或用 optional / map；INT_MIN 表示未访问需与题意区分

    function<int(int)> dfs = [&](int i) -> int {
        if (i == n) return 0;           // 边界举例
        if (memo[i] != INT_MIN) return memo[i];

        int best = /* 根据题意组合子问题 */;
        // best = max(dfs(i+1), dfs(i+2) + a[i]);  // 示意

        memo[i] = best;
        return best;
    };

    return dfs(0);
}

要点：同一状态只算一次，返回值写入 memo 后再返回。

---

4. 模板二：递推表（Bottom-up）

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

int solve_tab(const vector<int>& a) {
    const int n = (int)a.size();
    if (n == 0) return 0;

    vector<int> dp(n);
    dp[0] = a[0];                    // 边界举例
    for (int i = 1; i < n; ++i) {
        dp[i] = /* 由 dp[i-1], dp[i-2] ... 推出 */;
    }
    return dp[n - 1];
}

要点：循环顺序必须保证计算 dp[i] 时，所依赖的状态已经算好（DAG 拓扑序）。

---

5. 经典案例一：爬楼梯 / 斐波那契（线性 DP）

LeetCode 70. Climbing Stairs（与斐波那契同构）
每次爬 1 或 2 阶，问爬到 n 阶的方法数。

状态与转移

• 设 f[i] 为到达第 i 阶的方案数。
• f[i] = f[i-1] + f[i-2]，边界 f[0]=1, f[1]=1（或按题意调整下标）。

C++（空间优化到 O(1)）

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; ++i) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};

小结：线性 DP 常常可以把 dp 数组压成几个变量。

---

6. 经典案例二：打家劫舍（相邻不能选）

LeetCode 198. House Robber
非负数组 nums，不能抢相邻两家，求和最大。

状态与转移

• dp[i]：考虑前 i+1 间房（下标 0..i）能获得的最大金额。
• 对第 i 间：要么不抢 → dp[i-1]；要么抢 → nums[i] + dp[i-2]。

dp[i] = max(dp[i-1], nums[i] + (i>=2 ? dp[i-2] : 0))。

C++（O(n) 时间，O(1) 空间）

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

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0, prev1 = 0;
        for (int x : nums) {
            int cur = max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

---

7. 经典案例三：最长递增子序列（LIS）

LeetCode 300. Longest Increasing Subsequence
求严格递增子序列的最大长度。

状态与转移（O(n²)，易写）

• len[i]：以 nums[i] 结尾的 LIS 长度。
• len[i] = 1 + max{ len[j] | j < i 且 nums[j] < nums[i] }。

C++ 实现

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

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        const int n = (int)nums.size();
        if (n == 0) return 0;

        vector<int> len(n, 1);
        int ans = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    len[i] = max(len[i], len[j] + 1);
                }
            }
            ans = max(ans, len[i]);
        }
        return ans;
    }
};

进阶：用「耐心排序」维护数组 + 二分，可达到 O(n log n)。入门阶段先掌握 O(n²) 的状态定义即可。

---

8. 经典案例四：0-1 背包

LeetCode 416. Partition Equal Subset Sum 可化为：是否存在子集和为 sum/2。
核心是 0-1 背包：每件物品最多用一次。

状态与转移

• can[w]：能否用已考虑的若干物品凑出重量（或价值）和恰好为 w。
• 倒序更新一维数组，避免同一轮重复使用同一物品：

can[w] = can[w] || can[w - num]（在 w >= num 时）。

C++（一维 DP）

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

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = accumulate(nums.begin(), nums.end(), 0);
        if (s % 2) return false;
        int target = s / 2;

        vector<char> can(target + 1, 0);
        can[0] = 1;
        for (int x : nums) {
            for (int w = target; w >= x; --w) {
                if (can[w - x]) can[w] = 1;
            }
        }
        return can[target];
    }
};

要点：内层循环 从大到小 遍历容量，这是 0-1 背包一维实现的经典细节。

---

9. 经典案例五：完全背包（物品无限件）

与 0-1 的区别：每种物品可以用无限次。一维写法下，内层循环通常 从小到大 遍历容量，使得同一轮里可以反复叠加同一物品。

// 伪代码：求恰好装满容量 W 的方案数（示意）
vector<long long> dp(W + 1, 0);
dp[0] = 1;
for (int coin : coins) {
    for (int w = coin; w <= W; ++w) {
        dp[w] += dp[w - coin];
    }
}

LeetCode 322. Coin Change（最少硬币数）、518. Coin Change 2（方案数）都是完全背包的常见变体。

---

10. 常见 DP 题型速览

类型	典型状态	例子
线性	前缀 i、前两项	爬楼梯、打家劫舍、LIS
背包	容量 w、物品 i	0-1 / 完全 / 多重背包
区间	区间 [l,r]	矩阵链乘、戳气球、回文子串
树形	节点 u、是否选	打家劫舍 III
状态压缩	mask 表示集合	TSP、棋盘小范围放置

遇到区间题，可尝试：dp[l][r] = 枚举最后一步在 k 切开。

---

11. 复杂度与调试习惯

• 时间：大致为「状态数 × 每个状态的转移代价」。
• 空间：表的大小；注意能否滚动数组优化。
• 调试：打印小规模样例的手算表；检查边界 i=0、空数组、全零等。

---

12. 总结

动态规划 = 定义状态 + 写对转移 + 按正确顺序算一遍。

• 与回溯不同：回溯重在「枚举所有解」，DP 重在「重叠子问题 + 最优或计数」。
• 先写出暴力递归，标出参数即状态；再加 memo 或改成 for 循环填表。
• 0-1 背包一维要倒序，完全背包一维常要正序 —— 这是面试里极高频的细节。

把上述几道经典题写熟，再遇到新题时，你的第一反应应该是：「状态最少需要几个维度才能描述局面？」 答案往往就是突破口。

---

Happy Coding!