[动态规划问题详解]-程序员充电站

动态规划（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(不选, 选)。
边界条件：
- 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]; }