企业官网建设流程全解析

动态规划（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)）。

步骤拆解：

1. 状态定义：dp[i]表示第 i 个斐波那契数。
2. 转移方程：dp[i] = dp[i-1] + dp[i-2]。
3. 边界条件：dp[0] = 0，dp[1] = 1。
4. 遍历顺序：从 2 到 n 依次计算。
5. 结果：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，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

步骤拆解：

1. 状态定义：dp[i]表示以第 i 个元素结尾的最大子数组和。
2. 转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])（要么从当前元素重新开始，要么延续前一个子数组）。
3. 边界条件：dp[0] = nums[0]。
4. 遍历顺序：从 1 到 n-1。
5. 结果：遍历 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 网格的左上角出发，每次只能向下或向右移动，到达右下角共有多少条不同路径？

步骤拆解：

1. 状态定义：dp[i][j]表示从 (0,0) 到 (i,j) 的路径数。
2. 转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]（只能从上方或左方到达）。
3. 边界条件：
   • 第一行：dp[0][j] = 1（只能从左方来）。
   • 第一列：dp[i][0] = 1（只能从上方来）。
4. 遍历顺序：行优先遍历（从上到下，从左到右）。
5. 结果：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，求能装入背包的最大价值（每件物品只能选一次）。

步骤拆解：

1. 状态定义：dp[i][j]表示前 i 件物品，背包容量为 j 时的最大价值。
2. 转移方程：
   • 不选第 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(不选, 选)。
3. 边界条件：
   • dp[0][j] = 0（无物品时价值为 0）。
   • dp[i][0] = 0（容量为 0 时价值为 0）。
4. 遍历顺序：物品从 1 到 n，容量从 1 到 C。
5. 结果：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]; }

四、动态规划的常见优化技巧

1. 空间压缩：

   • 一维 DP→变量（如斐波那契）。
   • 二维 DP→一维 DP（如背包、不同路径）。
   • 仅保留必要的状态，丢弃无关的历史数据。

2. 状态合并：

   • 合并重复的状态定义，减少 DP 表维度（例如：将两个相关状态合并为一个）。

3. 单调队列优化：

   • 适用于状态转移涉及区间最值的问题（如滑动窗口最大值、多重背包）。

4. 滚动数组：

   • 对于只依赖前 k 层的二维 DP，用 k+1 个数组循环使用（如三维 DP 压缩为二维）。

五、动态规划的学习建议

1. 从基础模型入手：先掌握斐波那契、最大子数组和、背包、路径问题等经典模型，理解状态定义和转移的逻辑。
2. 多做分类练习：按 “一维 DP→二维 DP→区间 DP→树形 DP→状态压缩 DP” 的顺序进阶。
3. 手动推导 DP 表：对每个问题，先手动计算小案例的 DP 表（如 n=3、m=2），再写代码。
4. 对比暴力与 DP：理解 DP 如何通过缓存解决重叠子问题，避免重复计算。
5. 总结状态转移规律：例如 “以 i 结尾”“前 i 个元素”“到达 (i,j)” 等常见状态定义方式。

提炼与总结

• 动态规划的核心是状态定义 + 状态转移，状态定义是 “灵魂”，转移方程是 “核心”。
• 解题关键：将问题转化为 “子问题的最优解组合”，用 DP 表存储子问题解，避免重复计算。
• 优化核心：减少 DP 表的维度（空间）或减少状态转移的计算量（时间）。