动态规划完整讲解

一、动态规划核心思想

1. 本质

拆分重复子问题、记录中间结果、避免重复计算。 暴力递归会大量重复求解相同子问题，DP 用数组 / 哈希存储子问题答案，空间换时间。

2. 四大核心要素

1. 状态定义 dp [i] /dp [i][j]清晰描述dp数组代表什么含义，是 DP 最难一步。
2. 状态转移方程把大问题拆解为更小子问题，写出递推公式。
3. 初始条件（base case）最小子问题，不用推导、直接赋值。
4. 遍历顺序保证计算大状态时，依赖的子状态已经算完。

3. 适用场景判断（满足两个条件才能用 DP）

1. 最优子结构：大问题最优解由若干子问题最优解构成；
2. 重叠子问题：递归过程反复计算相同子问题。

4. 两种实现方式

1. 自顶向下：记忆化递归（备忘录）递归 + 缓存，遇到重复子问题直接查表，适合思考、代码短。
2. 自底向上：迭代 DP 数组从小到大循环填表，效率更高，无栈溢出，工程常用。

二、动态规划分类

类别 1：一维线性 DP（单数组 dp [i]）

特征：只有一个变化维度，线性数组递推

例题 1：斐波那契数列

题意

F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)，求第 n 项。

1. 状态定义：dp[i]= 第 i 个斐波那契数
2. 转移方程：dp[i] = dp[i-1] + dp[i-2]
3. base case：dp[0]=0，dp[1]=1

java

// 自底向上DP public int fib(int n) { if(n <= 1) return n; int[] dp = new int[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]; } // 空间优化：仅保存前两项 O(1)空间 public int fibOpt(int n) { if(n <= 1) return n; int a = 0, b = 1; for(int i = 2; i <= n; i++){ int c = a + b; a = b; b = c; } return b; }

例题 2：爬楼梯 LeetCode70

题意

一次爬 1 或 2 阶，求爬到 n 阶总方案数。

1. dp [i]：爬到第 i 阶的方案总数
2. 转移：dp[i] = dp[i-1] + dp[i-2]
3. base：dp[1]=1，dp[2]=2

例题 3：打家劫舍 LeetCode198

一维 DP，不能选相邻元素，求最大和。 dp [i]：前 i 户能偷的最大金额 转移：dp[i] = max(dp[i-1], dp[i-2]+nums[i])

类别 2：二维 DP（dp [i][j]，双维度）

场景 1：子序列 / 子串（两个下标代表两段区间）

例题 1：最长公共子序列 LCS LeetCode1143

字符串 s1 长度 m，s2 长度 n

1. dp [i][j]：s1 前 i 个字符、s2 前 j 个字符的最长公共子序列长度
2. 转移：
   • s1[i-1]==s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
   • 不相等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. base：dp[0][*]=0、dp[*][0]=0

例题 2：最长回文子串 LeetCode5

dp [i][j]：区间 [i,j] 是否为回文字符串 转移：s [i]==s [j] 且 (j-i<=2 || dp [i+1][j-1])

场景 2：网格路径（矩阵行走）

例题：不同路径 LeetCode62

m 行 n 列网格，只能右 / 下走，求从左上到右下路径数

1. dp [i][j]：走到 (i,j) 的路径总数
2. 转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. base：第一行、第一列全为 1

类别 3：背包 DP（最经典业务 DP 分类）

通用模型：给定容量，选物品求最值

1. 01 背包：物品只能选 1 次 dp [j]：容量 j 能装的最大价值 逆序遍历容量：dp[j] = max(dp[j], dp[j-w]+v)
2. 完全背包：物品无限选 正序遍历容量：dp[j] = max(dp[j], dp[j-w]+v)
3. 多重背包：物品限定 k 件
4. 分组背包：物品分多组，每组最多选一件

例题：零钱兑换 LeetCode322（完全背包）

dp [i]：凑金额 i 需要最少硬币数 转移：dp[i] = min(dp[i], dp[i-coins[k]]+1)

类别 4：区间 DP（dp [i][j]，区间 [i,j] 最优解）

特征：状态是一段连续区间，大区间由小区间合并而来

例题：石子合并

一堆石子分成左右两堆合并，代价为两堆重量和，求总最小代价。 dp [i][j]：合并 i~j 石子的最小代价 转移：枚举分割点 kdp[i][j] = min(dp[i][k]+dp[k+1][j]) + sum(i,j)遍历顺序：先算短区间，再算长区间。

类别 5：状态压缩 DP（二进制 DP）

特征：维度极大，用二进制数字代表状态，降低空间

常用于棋盘、子集、排列问题，旅行商 TSP 经典题。 dp [mask][u]：mask 二进制表示已访问城市集合，u 当前所在城市。

类别 6：树形 DP（树上动态规划）

特征：状态定义在树节点，子树为子问题

例题：二叉树打家劫舍 LeetCode337 每个节点存两个状态：

• dp [0]：不偷当前节点，子树最大值
• dp [1]：偷当前节点，子树最大值 后序遍历递归计算左右子树再合并。

三、DP 通用解题模板（做题固定流程）

1. 判断是否 DP：最优子结构 + 重叠子问题
2. 定义 dp 数组含义（最关键）
3. 找 base case 初始值
4. 推导状态转移方程
5. 确定循环遍历顺序（正序 / 逆序 / 区间长度从小到大）
6. 空间优化（可选）：二维转一维、滚动数组
7. 输出目标 dp 值

四、记忆化递归（自顶向下 DP 模板）

以爬楼梯举例：

java

运行

int[] memo; public int climbStairs(int n) { memo = new int[n+1]; Arrays.fill(memo, -1); return dfs(n); } int dfs(int i){ if(i == 1) return 1; if(i == 2) return 2; if(memo[i] != -1) return memo[i]; // 查表避免重复计算 memo[i] = dfs(i-1) + dfs(i-2); return memo[i]; }

五、一维 / 二维 DP 空间优化规律

1. 一维线性 DP：仅依赖前 1/2 项 → O (1) 变量替代数组；
2. 01 背包二维转一维：容量逆序，防止物品重复选取；
3. LCS、路径类二维 DP：可用滚动数组，只保存上一行数据。