动态规划 — 核心思想与经典问题

核心思想

DP = 记忆化搜索（自顶向下）或 递推填表（自底向上），本质是用空间换时间。

斐波那契：
  f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)

  递归树 — 大量重复计算
          f(5)
        /      \
     f(4)      f(3)
     /  \      /  \
  f(3) f(2) f(2) f(1)
   ↓ DP 解决
  数组 dp[n] 每个只算一次

时间：O(2ⁿ) → O(n)
空间：O(1)（只需两个变量）

DP 适用条件

条件	含义
最优子结构	大问题的最优解包含子问题最优解
重叠子问题	递归中反复遇到相同子问题
无后效性	当前状态确定后不受后续决策影响

0/1 背包

// 物品 i：重量 w[i]，价值 v[i]，背包容量 C
// dp[i][c] = 前 i 个物品，容量 c 的最大价值
int knapsack01(const vector<int> &w, const vector<int> &v, int C) {
    vector<int> dp(C + 1, 0);
    for (int i = 0; i < w.size(); ++i)
        for (int c = C; c >= w[i]; --c)  // ⚠️ 逆序：防止同物品多次使用
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    return dp[C];
}
// 时间 O(nC)，空间 O(C)

逆序原因：dp[c] 依赖 dp[c - w[i]]（上一行的值），正序会用到本行刚更新的值 = 物品被用了多次（变成完全背包）。

完全背包

// 每种物品无限件
int knapsackComplete(const vector<int> &w, const vector<int> &v, int C) {
    vector<int> dp(C + 1, 0);
    for (int i = 0; i < w.size(); ++i)
        for (int c = w[i]; c <= C; ++c)   // 正序：允许重用
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    return dp[C];
}

最长公共子序列 (LCS)

string lcs(const string &a, const string &b) {
    int n = a.size(), m = 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)
            dp[i][j] = (a[i-1] == b[j-1])
                ? dp[i-1][j-1] + 1
                : max(dp[i-1][j], dp[i][j-1]);

    // 回溯构建 LCS
    string res;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (a[i-1] == b[j-1]) { res += a[i-1]; --i; --j; }
        else if (dp[i-1][j] > dp[i][j-1]) --i;
        else --j;
    }
    reverse(res.begin(), res.end());
    return res;
}
// 时间 O(nm)，空间 O(nm) → 可优化到 O(min(n,m))

最长递增子序列 (LIS)

// 方法 1：DP O(n²)
int lisDP(const vector<int> &nums) {
    vector<int> dp(nums.size(), 1);
    int ans = 1;
    for (int i = 1; i < nums.size(); ++i)
        for (int j = 0; j < i; ++j)
            if (nums[j] < nums[i])
                ans = max(ans, dp[i] = max(dp[i], dp[j] + 1));
    return ans;
}

// 方法 2：贪心 + 二分 O(n log n)
int lisGreedy(const vector<int> &nums) {
    vector<int> tails;  // tails[i] = 长度为 i+1 的 LIS 的最小末尾
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

路径计数类 DP

// m×n 网格从左上到右下的路径数（只能右/下）
// dp[i][j] = dp[i-1][j] + dp[i][j-1]
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < m; ++i)
        for (int j = 1; j < n; ++j)
            dp[j] += dp[j-1];
    return dp[n-1];
}
// 数学解：C(m+n-2, m-1)

DP 解题模板

1. 定义 dp[i] 或 dp[i][j] 的含义
2. 写出状态转移方程
3. 确定初始条件（base case）
4. 确定遍历顺序（正序/逆序，外层/内层）
5. 空间优化（滚动数组）

特征识别：
  - "最值" → 考虑 DP
  - "方案数" → 考虑 DP
  - "能不能达到" → 考虑 DP（布尔型）