动态规划（Dynamic Programming，DP）是算法设计中的核心思想之一，核心是将复杂问题分解为重叠的子问题，通过存储子问题的解来避免重复计算，最终推导出原问题的最优解。以下从核心原理、解题步骤、经典模型到实战案例，为你系统拆解动态规划：
一、动态规划的核心基础
1. 核心思想
- 最优子结构：原问题的最优解包含其子问题的最优解（子问题的解可以组合出原问题的解）。
- 重叠子问题：求解原问题时会反复遇到相同的子问题（若暴力递归会重复计算，DP 通过缓存避免）。
- 无后效性：子问题的解一旦确定，不受后续决策影响（即当前状态只依赖过去的状态，与未来无关）。
2. 与其他算法的区别
| 算法 | 核心特点 | 适用场景 |
|---|---|---|
| 暴力递归 | 直接分解问题，无缓存 | 子问题无重叠（否则效率极低） |
| 记忆化搜索 | 递归 + 缓存（自顶向下） | 子问题重叠，递归思路清晰 |
| 动态规划 | 迭代 + 状态表（自底向上） | 子问题重叠，需最优解 |
二、动态规划的解题步骤（黄金五步）
1. 定义状态（最关键）
- 用
dp[i]或dp[i][j]表示 “某个子问题的最优解”，明确状态的含义（例如：dp[i]表示前 i 个元素的最大和）。 - 状态定义的好坏直接决定 DP 是否能实现，需紧扣问题目标。
2. 确定状态转移方程
- 描述 “如何从子问题的解推导出原问题的解”，即
dp[i] = f(dp[i-1], dp[i-2], ...)。 - 核心：找到当前状态与之前状态的依赖关系。
3. 初始化边界条件
- 确定最小子问题的解（即 DP 表的初始值），例如：
dp[0] = 0、dp[1] = nums[0]。 - 边界条件错误会导致整个 DP 表计算错误。
4. 确定遍历顺序
- 根据状态转移方程，确定计算 DP 表的顺序（例如：从前到后、从后到前、二维表的行优先 / 列优先）。
- 确保计算当前状态时，其依赖的子问题已被计算。
5. 计算最终结果
- 原问题的解对应 DP 表中的某个位置（例如：
dp[n]或dp[n][m]）。
三、经典动态规划模型
模型 1：一维 DP—— 斐波那契数列
问题：求第 n 个斐波那契数（F (0)=0, F (1)=1, F (n)=F (n-1)+F (n-2)）。
步骤拆解：
- 状态定义：
dp[i]表示第 i 个斐波那契数。 - 转移方程：
dp[i] = dp[i-1] + dp[i-2]。 - 边界条件：
dp[0] = 0，dp[1] = 1。 - 遍历顺序：从 2 到 n 依次计算。
- 结果：
dp[n]。
int fib(int n) { if (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]; }优化：由于只依赖前两个状态，可省略 DP 表，用变量存储：
int fib(int n) { if (n <= 1) return n; int a = 0, b = 1, c; for (int i = 2; i <= n; ++i) { c = a + b; a = b; b = c; } return b; }模型 2：一维 DP—— 最大子数组和（LeetCode 53）
问题：给定整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
步骤拆解：
- 状态定义：
dp[i]表示以第 i 个元素结尾的最大子数组和。 - 转移方程：
dp[i] = max(nums[i], dp[i-1] + nums[i])（要么从当前元素重新开始，要么延续前一个子数组）。 - 边界条件：
dp[0] = nums[0]。 - 遍历顺序：从 1 到 n-1。
- 结果：遍历 dp 数组取最大值。
int maxSubArray(vector<int>& nums) { int n = nums.size(); vector<int> dp(n); dp[0] = nums[0]; int result = dp[0]; for (int i = 1; i < n; ++i) { dp[i] = max(nums[i], dp[i-1] + nums[i]); result = max(result, dp[i]); } return result; }优化：省略 DP 表，用变量存储当前状态：
int maxSubArray(vector<int>& nums) { int cur_sum = nums[0], max_sum = nums[0]; for (int i = 1; i < nums.size(); ++i) { cur_sum = max(nums[i], cur_sum + nums[i]); max_sum = max(max_sum, cur_sum); } return max_sum; }模型 3：二维 DP—— 不同路径（LeetCode 62）
问题：一个机器人从 m×n 网格的左上角出发，每次只能向下或向右移动，到达右下角共有多少条不同路径？
步骤拆解：
- 状态定义：
dp[i][j]表示从 (0,0) 到 (i,j) 的路径数。 - 转移方程：
dp[i][j] = dp[i-1][j] + dp[i][j-1]（只能从上方或左方到达）。 - 边界条件：
- 第一行：
dp[0][j] = 1（只能从左方来）。 - 第一列：
dp[i][0] = 1（只能从上方来）。
- 第一行：
- 遍历顺序：行优先遍历（从上到下，从左到右）。
- 结果：
dp[m-1][n-1]。
int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 1)); // 初始化边界为1 for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-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]; // 等价于 dp[i][j] = dp[i-1][j] + dp[i][j-1] } } return dp[n-1]; }模型 4：二维 DP——0-1 背包问题
问题：有 n 件物品，每件物品的重量为 w [i]，价值为 v [i]，背包容量为 C，求能装入背包的最大价值（每件物品只能选一次）。
步骤拆解：
- 状态定义：
dp[i][j]表示前 i 件物品，背包容量为 j 时的最大价值。 - 转移方程：
- 不选第 i 件物品：
dp[i][j] = dp[i-1][j]。 - 选第 i 件物品（需 j ≥ w [i]）：
dp[i][j] = dp[i-1][j - w[i]] + v[i]。 - 最终：
dp[i][j] = max(不选, 选)。
- 不选第 i 件物品：
- 边界条件：
dp[0][j] = 0（无物品时价值为 0）。dp[i][0] = 0（容量为 0 时价值为 0）。
- 遍历顺序：物品从 1 到 n，容量从 1 到 C。
- 结果：
dp[n][C]。
int knapsack(vector<int>& w, vector<int>& v, int C) { int n = w.size(); vector<vector<int>> dp(n+1, vector<int>(C+1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= C; ++j) { if (j < w[i-1]) { // 容量不足，无法选第i件（注意w[i-1]是第i件物品的重量） dp[i][j] = dp[i-1][j]; } else { dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1]); } } } return dp[n][C]; }优化：一维数组压缩（容量需从后往前遍历，避免覆盖未计算的状态）：
int knapsack(vector<int>& w, vector<int>& v, int C) { int n = w.size(); vector<int> dp(C+1, 0); for (int i = 0; i < n; ++i) { // 遍历物品 for (int j = C; j >= w[i]; --j) { // 从后往前遍历容量 dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } return dp[C]; }四、动态规划的常见优化技巧
空间压缩：
- 一维 DP→变量（如斐波那契）。
- 二维 DP→一维 DP（如背包、不同路径）。
- 仅保留必要的状态，丢弃无关的历史数据。
状态合并：
- 合并重复的状态定义，减少 DP 表维度（例如：将两个相关状态合并为一个）。
单调队列优化：
- 适用于状态转移涉及区间最值的问题（如滑动窗口最大值、多重背包）。
滚动数组：
- 对于只依赖前 k 层的二维 DP，用 k+1 个数组循环使用（如三维 DP 压缩为二维）。
五、动态规划的学习建议
- 从基础模型入手：先掌握斐波那契、最大子数组和、背包、路径问题等经典模型，理解状态定义和转移的逻辑。
- 多做分类练习：按 “一维 DP→二维 DP→区间 DP→树形 DP→状态压缩 DP” 的顺序进阶。
- 手动推导 DP 表：对每个问题，先手动计算小案例的 DP 表（如 n=3、m=2），再写代码。
- 对比暴力与 DP：理解 DP 如何通过缓存解决重叠子问题，避免重复计算。
- 总结状态转移规律：例如 “以 i 结尾”“前 i 个元素”“到达 (i,j)” 等常见状态定义方式。
提炼与总结
- 动态规划的核心是状态定义 + 状态转移，状态定义是 “灵魂”，转移方程是 “核心”。
- 解题关键：将问题转化为 “子问题的最优解组合”，用 DP 表存储子问题解，避免重复计算。
- 优化核心：减少 DP 表的维度（空间）或减少状态转移的计算量（时间）。
