C++ 算法技巧 — 动态规划 (Dynamic Programming)

章节概述

动态规划 (Dynamic Programming, DP) 是解决最优化问题的一种方法，它将原问题分解为相互
重叠的子问题，先求解子问题的最优值，再递推得到原问题的最优解。

DP 的两个核心性质：

最优子结构 (Optimal Substructure) — 问题的最优解包含子问题的最优解
重叠子问题 (Overlapping Subproblems) — 子问题被反复计算，需要缓存结果避免重复

DP 与贪心的区别：贪心每步做局部最优且不回头；DP 考虑所有可能的转移，选择全局最优。

DP 与分治的区别：分治的子问题不重叠（如归并排序左右两半不重复）；DP 的子问题大量重叠。

核心原理

1. 状态定义 — DP 的根基

设 $d p [i]$ 表示以 $i$ 结尾/前 $i$ 个元素的某个最优值。状态定义决定了整个 DP 的走向。

2. 状态转移方程 — DP 的灵魂

线性 DP 通用形式:
dp[i] = max/min/sum { dp[j] + cost(j, i) }  (j < i)
边界: dp[0] = initial_value

3. 记忆化 vs 递推

方法	方向	实现	空间
记忆化搜索 (Top-Down)	自顶向下	递归 + 缓存数组	O(n) 递归栈 + O(n) 缓存
递推 (Bottom-Up)	自底向上	循环迭代	O(n) 或 O(1) 滚动优化

4. 关键数学技巧

滚动数组: 当 $d p [i]$ 仅依赖 $d p [i - 1]$ 和 $d p [i - 2]$ 时，空间从 O(n) 降到 O(1)
逆序遍历: 0/1 背包一维优化中，容量逆序遍历保证每件物品只选一次
正序遍历: 完全背包中，容量正序遍历允许物品无限次选取

关键数据结构

DP 的核心是数组递推，依赖以下数据结构：

A_容器_Container — vector 用于 DP 状态存储（一维/二维 DP 表）
C_堆_Heap — 优先队列可优化部分 DP（如 Dijkstra 本质 = DP + 贪心）
F_队列_Queue — 单调队列优化部分 DP（如单调队列优化多重背包）

第一节: 基础概念 + 数学原理

1.1 从斐波那契数列理解 DP 的诞生

斐波那契数列定义：

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)  (n >= 2)

朴素递归 (存在大量重复计算)：

F(5)
├── F(4)
│   ├── F(3)
│   │   ├── F(2)  ← 重复计算
│   │   │   ├── F(1)
│   │   │   └── F(0)
│   │   └── F(1)
│   └── F(2)  ← 重复计算
│       ├── F(1)
│       └── F(0)
└── F(3)  ← 重复计算
    ├── F(2)  ← 重复计算
    │   ├── F(1)
    │   └── F(0)
    └── F(1)

F(2) 被计算了 3 次，F(3) 被计算了 2 次。随着 n 增大，重复计算呈指数增长，时间复杂度 O(2

1.2 方法一：记忆化搜索 (Top-Down, Memoization)

递归 + 缓存：将已计算的结果存入数组，遇到相同子问题时直接查表。

#include <iostream>
#include <vector>
using namespace std;
 
vector<long long> memo(100, -1);  // -1 表示未计算
 
long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];   // 查缓存
    return memo[n] = fib(n - 1) + fib(n - 2); // 计算并缓存
}
 
int main() {
    cout << "F(50) = " << fib(50) << endl;
    return 0;
}

时间: O(n) — 每个子问题只计算一次
空间: O(n) — 缓存数组 + O(n) 递归栈

1.3 方法二：递推 (Bottom-Up, Tabulation)

将递归调用逐层展开为循环递推。DP 的最终形态。

数学推导:

已知: F(0) = 0, F(1) = 1
递推: F(2) = F(1) + F(0) = 1 + 0 = 1
递推: F(3) = F(2) + F(1) = 1 + 1 = 2
递推: F(4) = F(3) + F(2) = 2 + 1 = 3
递推: F(5) = F(4) + F(3) = 3 + 2 = 5
递推: F(6) = F(5) + F(4) = 5 + 3 = 8

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n = 50;
    vector<long long> dp(n + 1);
    dp[0] = 0;    // 边界条件
    dp[1] = 1;    // 边界条件
 
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];  // 状态转移方程
 
    cout << "F(50) = " << dp[50] << endl;
    return 0;
}

时间: O(n), 空间: O(n)

1.4 方法三：滚动数组优化 (空间 O(1))

观察：F(n) 只依赖于 F(n-1) 和 F(n-2)，不需要存全部历史。

#include <iostream>
using namespace std;
 
int main() {
    int n = 50;
    long long a = 0, b = 1;  // a = F(0), b = F(1)
 
    for (int i = 2; i <= n; i++) {
        long long c = a + b;  // F(i) = F(i-2) + F(i-1)
        a = b;                // F(i-2) ← F(i-1)
        b = c;                // F(i-1) ← F(i)
    }
 
    cout << "F(50) = " << b << endl;
    return 0;
}

时间: O(n), 空间: O(1)

1.5 DP 的通用解题框架

flowchart TD
    A["分析问题: 是否具有最优子结构?"] --> B["定义状态: dp[i] 表示什么?"]
    B --> C["建立转移方程: dp[i] 由哪些子状态推导?"]
    C --> D["确定边界条件: dp[0] 等初始值"]
    D --> E["确定计算顺序: 从哪个方向递推?"]
    E --> F["编写代码 + 滚动数组优化空间（可选）"]
    F --> G["验证: 用小规模测试用例自测"]

1.6 0/1 背包的数学形式

设 dp[i][w] 为前 i 件物品放入容量 w 的背包的最大价值

dp[i][w] = max(
    dp[i-1][w],               // 不选第 i 件
    dp[i-1][w - weight[i]] + value[i]  // 选第 i 件 (当 w >= weight[i])
)

边界: dp[0][w] = 0  (0 件物品的价值为 0)
      dp[i][0] = 0  (容量为 0 时价值为 0)

第二节: 经典 DP 模型与代码

2.1 爬楼梯问题 (Climbing Stairs)

问题: 有 n 级楼梯，每次可以爬 1 级或 2 级。问爬到第 n 级有多少种方法。

分析:

状态: dp[i] = 爬到第 i 级的方法数
转移: dp[i] = dp[i-1] + dp[i-2]（从 i-1 走 1 步或从 i-2 走 2 步）
边界: dp[0] = 1（不爬是一种方法）, dp[1] = 1
本质: 斐波那契数列 f[n+1]

爬楼梯 n=4 的递推:
dp[0] = 1
dp[1] = 1
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
         方案: 1,1  和  2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
         方案: 1,1,1  /  1,2  /  2,1
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
         方案: 1,1,1,1 / 1,1,2 / 1,2,1 / 2,1,1 / 2,2

#include <iostream>
#include <vector>
using namespace std;
 
int climbStairs(int n) {
    if (n <= 1) return 1;
    vector<int> dp(n + 1);
    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 << "爬到第 10 级: " << climbStairs(10) << " 种方法" << endl;
    return 0;
}

2.2 最大子数组和 (Maximum Subarray, Kadane)

问题: 给定整数数组，求连续子数组的最大和。

分析:

状态: dp[i] = 以 i 结尾的连续子数组的最大和
转移: dp[i] = max(nums[i], dp[i-1] + nums[i])
- 要么前面丢弃（从 i 重新开始），要么继承前面的和
答案: max(dp[0], dp[1], …, dp[n-1])

递推过程：

nums: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
i=0: dp=-2    => maxSoFar = -2
i=1: dp=max(1, -2+1)=1   => maxSoFar = 1
i=2: dp=max(-3, 1-3)=-2  => maxSoFar = 1
i=3: dp=max(4, -2+4)=4   => maxSoFar = 4
i=4: dp=max(-1, 4-1)=3   => maxSoFar = 4
i=5: dp=max(2, 3+2)=5    => maxSoFar = 5
i=6: dp=max(1, 5+1)=6    => maxSoFar = 6  ← 最大值
i=7: dp=max(-5, 6-5)=1   => maxSoFar = 6
i=8: dp=max(4, 1+5)=5    => maxSoFar = 6

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int maxSubArray(vector<int>& nums) {
    int dp = nums[0];     // 以当前结尾的最大和
    int ans = nums[0];    // 全局最大和
    for (int i = 1; i < nums.size(); i++) {
        dp = max(nums[i], dp + nums[i]);
        ans = max(ans, dp);
    }
    return ans;
}
 
int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "最大子数组和: " << maxSubArray(nums) << endl;
    // 输出: 6  (子数组 [4, -1, 2, 1])
    return 0;
}

时间: O(n), 空间: O(1)。这个算法也叫 Kadane’s Algorithm。

2.3 0/1 背包问题 (0/1 Knapsack)

问题: 有 N 件物品，第 i 件重量 w[i]、价值 v[i]。背包容量 W。每件物品只能选或不选，
求最大总价值。

二维 DP 推导:

dp[i][w] = 前 i 件物品放入容量 w 的背包的最大价值

决策: 对第 i 件物品:
  - 不选: dp[i][w] = dp[i-1][w]
  - 选入: dp[i][w] = dp[i-1][w - w[i]] + v[i]  (前提: w >= w[i])

转移: dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i])

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int knapsack01(vector<int>& w, vector<int>& v, int W) {
    int n = 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 = {2, 3, 4, 5};
    vector<int> v = {3, 4, 5, 6};
    int W = 8;
    cout << "最大价值: " << knapsack01(w, v, W) << endl;
    // 输出: 10
    return 0;
}

2.4 空间优化：一维滚动数组

观察：dp[i][w] 只依赖 dp[i-1][…]（上一行），可以用一维数组 + 逆序循环优化空间。

关键: 容量 j 必须从大到小遍历，保证 dp[j - w[i]] 是”上一行”（旧值）而非”本行”（新值）。

逆序遍历的意义（物品重量=2, 价值=3）:

正向遍历（错误）:
  j=2: dp[2] = max(dp[2], dp[0]+3) = 3
  j=4: dp[4] = max(dp[4], dp[2]+3) = 6  ← 错误! dp[2]已更新为新值(本行)

逆序遍历（正确）:
  j=5: dp[5] = max(dp[5], dp[3]+3) = dp[3]仍是旧值(上一行)
  j=4: dp[4] = max(dp[4], dp[2]+3) = dp[2]仍是旧值
  j=3: dp[3] = max(dp[3], dp[1]+3)
  j=2: dp[2] = max(dp[2], dp[0]+3)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int knapsack01_1D(vector<int>& w, vector<int>& v, int W) {
    vector<int> dp(W + 1, 0);
 
    for (int i = 0; i < w.size(); i++) {
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}
 
int main() {
    vector<int> w = {2, 3, 4, 5};
    vector<int> v = {3, 4, 5, 6};
    int W = 8;
    cout << "最大价值: " << knapsack01_1D(w, v, W) << endl;
    return 0;
}

时间: O(n * W), 空间: O(W)

2.5 完全背包 (Unbounded Knapsack)

问题: 每件物品可以选无限次。

与 0/1 背包的唯一区别: 容量 j 变更为正序遍历。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int knapsackComplete(vector<int>& w, vector<int>& v, int W) {
    vector<int> dp(W + 1, 0);
 
    for (int i = 0; i < w.size(); i++) {
        for (int j = w[i]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}
 
int main() {
    vector<int> w = {2, 3, 4};
    vector<int> v = {3, 4, 5};
    int W = 8;
    cout << "完全背包最大价值: " << knapsackComplete(w, v, W) << endl;
    // 输出: 12  (4个物品1: 重量2x4=8, 价值3x4=12)
    return 0;
}

2.6 最长上升子序列 (Longest Increasing Subsequence, LIS)

问题: 给定无序数组，求最长严格递增子序列的长度。

分析:

状态: dp[i] = 以 nums[i] 结尾的最长上升子序列长度
转移: dp[i] = max{dp[j] + 1} (对所有 j < i 且 nums[j] < nums[i])
答案: max(dp[0], …, dp[n-1])

数组: [10, 9, 2, 5, 3, 7, 101, 18]
递推:
i=0, nums[0]=10: dp[0] = 1                     => dp=[1,1,1,2,2,3,4,4]
i=3, nums[3]=5:  比5小的有2 => dp[2]+1=2
i=5, nums[5]=7:  比7小的最大dp=3 => 3
i=6, nums[6]=101: 比101小的最大dp=3 => 4
答案: max(dp) = 4, 子序列: [2, 3, 7, 101]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int LIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ans = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}
 
int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "LIS 长度: " << LIS(nums) << endl;
    // 输出: 4
    return 0;
}

时间: O(n^2)，空间: O(n)
(另有用二分优化的 O(n log n) 解法，见进阶阅读)

2.7 最长公共子序列 (Longest Common Subsequence, LCS)

问题: 给定两个字符串，求最长的公共子序列（不要求连续）。

分析:

状态: dp[i][j] = s1 前 i 个字符与 s2 前 j 个字符的 LCS 长度
转移:
- 若 s1[i] == s2[j]：dp[i][j] = dp[i-1][j-1] + 1
- 若 s1[i] != s2[j]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

s1 = "abcde", s2 = "ace"
dp 表格:

    ""  a  c  e
""   0  0  0  0
a    0  1  1  1     s1[0]=a, s2[0]=a => dp[1][1]=dp[0][0]+1=1
b    0  1  1  1     s1[1]=b, 不匹配 => dp[2]=max(上,左)=1
c    0  1  2  2     s1[2]=c, c==c => dp[3][2]=dp[2][1]+1=2
d    0  1  2  2
e    0  1  2  3     s1[4]=e, e==e => dp[5][3]=3

LCS = 3, 子序列 "ace"

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int LCS(string s1, string s2) {
    int n = s1.size(), m = s2.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 (s1[i - 1] == s2[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() {
    string s1 = "abcde", s2 = "ace";
    cout << "LCS: " << LCS(s1, s2) << endl;
    // 输出: 3
    return 0;
}

时间: O(nm), 空间: O(nm) (可优化到 O(min(n,m)) 用滚动数组)

2.8 编辑距离 (Edit Distance / Levenshtein Distance)

问题: 将 word1 转换为 word2，每次可执行插入/删除/替换一个字符，求最少操作数。

分析:

状态: dp[i][j] = word1 前 i 个字符转换为 word2 前 j 个字符的最少操作数
转移:
- 若 word1[i] == word2[j]：dp[i][j] = dp[i-1][j-1]（不需要操作）
- 否则：取三者最小值 + 1
  - 替换: dp[i-1][j-1] + 1
  - 删除: dp[i-1][j] + 1
  - 插入: dp[i][j-1] + 1

word1 = "horse", word2 = "ros"
dp 表格:

       ""  r  o  s
""      0  1  2  3    (全部插入)
h       1  1  2  3
o       2  2  1  2    ho→ro: o==o 无需操作
r       3  2  2  2
s       4  3  3  2
e       5  4  4  3    horse→ros: 删除e (dp[4][3]+1=3)

答案: 3 (horse → rorse → rose → ros = 3步)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int minDistance(string word1, string word2) {
    int n = word1.size(), m = word2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
 
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min({
                    dp[i - 1][j],      // 删除
                    dp[i][j - 1],      // 插入
                    dp[i - 1][j - 1]   // 替换
                });
        }
    }
    return dp[n][m];
}
 
int main() {
    cout << "horse → ros: " << minDistance("horse", "ros") << " 步" << endl;
    // 输出: 3
    return 0;
}

第三节: 进阶 DP 模型

3.1 区间 DP (Interval DP)

问题模板: 将一个大区间的最优解拆分为子区间的最优解。

典型问题: 石子合并 — n 堆石子排成一排，每次合并相邻两堆代价为两堆石子数之和，
求合并成一堆的最小代价。

状态: dp[l][r] = 合并区间 [l, r] 的最小代价

转移: dp[l][r] = min_{k=l}^{r-1} { dp[l][k] + dp[k+1][r] + sum[l..r] }

石子: [3, 4, 5]
区间长度=1: dp[0][0]=0, dp[1][1]=0, dp[2][2]=0
区间长度=2:
  dp[0][1] = 0+0+(3+4) = 7
  dp[1][2] = 0+0+(4+5) = 9
区间长度=3:
  k=0: 0+9+12 = 21
  k=1: 7+0+12 = 19  ← 最优
答案: 19

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int mergeStones(vector<int>& stones) {
    int n = stones.size();
    vector<int> pre(n + 1, 0);
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + stones[i - 1];
 
    vector<vector<int>> dp(n, vector<int>(n, 1e9));
    for (int i = 0; i < n; i++) dp[i][i] = 0;
 
    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            int sum_lr = pre[r + 1] - pre[l];
            for (int k = l; k < r; k++) {
                dp[l][r] = min(dp[l][r],
                               dp[l][k] + dp[k + 1][r] + sum_lr);
            }
        }
    }
    return dp[0][n - 1];
}
 
int main() {
    vector<int> stones = {3, 4, 5};
    cout << "石子合并最小代价: " << mergeStones(stones) << endl;
    // 输出: 19
    return 0;
}

时间: O(n^3), 空间: O(n

3.2 背包问题变体：求方案数

问题: 给定面额为 coins 的硬币，每种无限个。求凑出金额 amount 的方案数。

#include <iostream>
#include <vector>
using namespace std;
 
int coinChangeWays(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
 
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] += dp[j - coin];
        }
    }
    return dp[amount];
}
 
int main() {
    vector<int> coins = {1, 2, 5};
    cout << "凑出5元的方案数: " << coinChangeWays(coins, 5) << endl;
    // dp[5] = 4    方案: (1,1,1,1,1), (2,1,1,1), (2,2,1), (5)
    return 0;
}

3.3 背包问题变体：最少硬币数

问题: 给定面额 coins，每种无限个。求凑出 amount 的最少硬币数，无法凑出返回 -1。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
int coinChangeMin(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
 
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            if (dp[j - coin] != INT_MAX)
                dp[j] = min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}
 
int main() {
    vector<int> coins = {1, 2, 5};
    cout << "凑出11元的最少硬币: " << coinChangeMin(coins, 11) << endl;
    // 输出: 3  (5+5+1=11)
    return 0;
}

题号	题目	难度	知识点
P1048 采药	采药	普及-	0/1 背包
P1049 装箱问题	装箱问题	普及-	0/1 背包
P1115 最大子段和	最大子段和	普及-	线性 DP
P1616 疯狂的采药	疯狂的采药	普及-	完全背包
P1439 LCS	最长公共子序列	提高	LIS 优化
P1020 导弹拦截	导弹拦截	普及+/提高	LIS + 贪心
P1775 石子合并	石子合并(弱化版)	普及+/提高	区间 DP
P2758 编辑距离	编辑距离	普及	编辑距离 DP

RootStack

探索