DP核心框架

动态规划是什么？

动态规划问题的一般形式是求最值。核心思想是穷举所有可行解，再从中找出最值。
难点在于：

• 如何正确穷举 → 需要状态转移方程（递归思维）
• 是否具备最优子结构（子问题独立）
• 重叠子问题的优化 → 用备忘录或 DP table

动态规划三要素：重叠子问题、最优子结构、状态转移方程。

---

解题通用框架

按顺序思考：

1. 明确状态（会变化的量）
2. 明确选择（导致状态变化的行为）
3. 定义 dp 数组/函数的含义

代码框架（C++ 示意）

自顶向下（递归+备忘录）

#include <bits/stdc++.h>
using namespace std;

int dp(状态1, 状态2, ...) {
    int res = 最值初始值;
    for (选择 : 所有可能的选择) {
        res = 最值(res, dp(新状态));
    }
    return res;
}

自底向上（迭代DP table）

#include <bits/stdc++.h>
using namespace std;

// 初始化 边界条件
dp[0][0][...] = 边界条件;
// 状态转移
for (状态1 : 状态1的所有取值)
    for (状态2 : 状态2的所有取值)
        for (...)
            dp[状态1][状态2][...] = 最值(选择1, 选择2, ...);

---

例1：斐波那契数列

LeetCode 509，主要演示重叠子问题的消除，不涉及求最值。

1. 暴力递归

状态转移方程：

#include <bits/stdc++.h>
using namespace std;

int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n - 1) + fib(n - 2);
}

递归树节点数 (O(2^n))，大量重复计算（重叠子问题）。

2. 带备忘录的递归（自顶向下）

用一维数组记录已计算的值，剪枝避免重复。

#include <bits/stdc++.h>
using namespace std;

int dp(vector<int>& memo, int n) {
    if (n == 0 || n == 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
}

int fib(int n) {
    vector<int> memo(n + 1, -1);
    return dp(memo, n);
}

时间复杂度 (O(n))。

3. DP table 迭代（自底向上）

#include <bits/stdc++.h>
using namespace std;

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

本质与备忘录相同，视角不同。

4. 空间优化

只保留前两个状态，空间复杂度 (O(1))。

#include <bits/stdc++.h>
using namespace std;

int fib(int n) {
    if (n == 0 || n == 1) return n;
    int dp_i_1 = 1, dp_i_2 = 0;
    for (int i = 2; i <= n; ++i) {
        int dp_i = dp_i_1 + dp_i_2;
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
}

小结：状态转移方程就是暴力解法的数学表达，写出暴力解 = 找到状态转移方程。剩下的优化只是消除重叠子问题。

---

例2：零钱兑换

LeetCode 322，展示最优子结构和状态转移方程的建立。

1. 确认最优子结构

凑出 amount=11 的最少硬币数，可由凑出 10,9,6 的最少硬币数 + 一枚硬币得到，子问题互相独立。

2. 状态转移方程三步走

• 状态：目标金额 n
• 选择：选一枚硬币 coin，状态变为 n - coin
• dp 定义：dp(n) = 凑出金额 n 所需的最少硬币数

状态转移方程：

3. 暴力递归

#include <bits/stdc++.h>
using namespace std;

int dp(vector<int>& coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    int res = INT_MAX;
    for (int coin : coins) {
        int subProblem = dp(coins, amount - coin);
        if (subProblem == -1) continue;
        res = min(res, subProblem + 1);
    }
    return res == INT_MAX ? -1 : res;
}

int coinChange(vector<int>& coins, int amount) {
    return dp(coins, amount);
}

最坏时间复杂度 (O(k^n))，重叠子问题严重。

4. 带备忘录的递归

#include <bits/stdc++.h>
using namespace std;

int dp(vector<int>& coins, int amount, vector<int>& memo) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    if (memo[amount] != -666) return memo[amount];
    int res = INT_MAX;
    for (int coin : coins) {
        int subProblem = dp(coins, amount - coin, memo);
        if (subProblem == -1) continue;
        res = min(res, subProblem + 1);
    }
    memo[amount] = (res == INT_MAX) ? -1 : res;
    return memo[amount];
}

int coinChange(vector<int>& coins, int amount) {
    vector<int> memo(amount + 1, -666);
    return dp(coins, amount, memo);
}

时间复杂度降为 (O(kn))。

5. DP table 迭代

dp[i] 表示凑出金额 i 的最少硬币数，初始化为一个较大的数（如 amount+1）。

#include <bits/stdc++.h>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 0; i <= amount; ++i) {
        for (int coin : coins) {
            if (i - coin < 0) continue;
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

---

核心总结

计算机只会穷举，算法设计就是：「如何穷举」→「如何聪明地穷举」

1. 状态转移方程 → 解决“如何穷举”

   • 明确状态、选择、dp 定义，直接对应暴力递归

2. 备忘录 / DP table → 解决“如何聪明地穷举”

   • 用空间换时间，消除重叠子问题
   • 自顶向下与自底向上本质相同

3. 后续学习要点

   • 二维 DP 压缩到一维（滚动数组）
   • 识别问题包装（如爬楼梯 = 斐波那契）
   • 多练习，养成“找状态、找选择”的思维习惯

掌握这个框架，大部分动态规划问题都能按部就班地解决。

*学习笔记

暂没有学习笔记，快来抢first blood ！