11 种动态规划（DP）完整讲解

动态规划的核心是 “拆分重叠子问题，存储子问题解以避免重复计算”，本质是 “递推 + 记忆化”。以下从问题本质出发，结合数学逻辑和典型例题，系统讲解 11 种 DP 类型。

一、线性 DP：基于线性序列的递推

1. 核心逻辑

状态与 “线性序列的前 i 个元素” 绑定，递推顺序沿序列方向（从左到右 / 从右到左），每个状态仅依赖前序有限个状态，适用于序列类优化问题。

2. 模型与公式（以最长上升子序列 LIS 为例）

• 问题：给定序列a[1..n]，求严格递增的最长子序列长度。

• 状态定义：dp[i] = 以a[i]结尾的最长上升子序列长度。

• 递推逻辑：若j < i且a[j] < a[i]，则a[i]可接在a[j]的子序列后，此时dp[i]可更新为dp[j]+1；否则dp[i]默认值为 1（自身为子序列）。

• 公式：

(dp[i] = \max_{1 \leq j < i, a[j] < a[i]} (dp[j] + 1) \quad (初始化dp[i]=1))

• 结果：max(dp[1..n])

3. 实例

序列[10,9,2,5,3,7,101,18]：

计算得dp = [1,1,1,2,2,3,4,4]，最长上升子序列长度为 4（如[2,3,7,18]）。

二、区间 DP：基于区间的递推

1. 核心逻辑

状态与 “区间[l,r]” 绑定，递推顺序按 “区间长度递增”（先算短区间，再用短区间结果推长区间），适用于区间类优化问题（如合并、分割）。

2. 模型与公式（以石子合并问题为例）

• 问题：n 堆石子排成一排，每次合并相邻两堆，代价为两堆总和，求合并为一堆的最小代价。

• 状态定义：dp[l][r] = 合并区间[l,r]石子的最小代价；sum[l][r] = 区间[l,r]石子总和（用前缀和s[r]-s[l-1]计算，s[0]=0）。

• 递推逻辑：将[l,r]拆分为[l,k]和[k+1,r]（l≤k<r），总代价为 “合并子区间代价 + 当前合并代价”，取最小值。

• 公式：

(dp[l][r] = \min_{l \leq k < r} (dp[l][k] + dp[k+1][r] + sum[l][r]))

• 边界：l=r时，dp[l][r]=0（无需合并）；结果：dp[1][n]

3. 实例

石子[1,3,5,2]：

前缀和s=[0,1,4,9,11]，计算得dp[1][4]=22（最小代价）。

三、背包 DP：资源限制下的选择优化

分三类，核心是 “容量约束下的价值最大化”，差异在于物品选择次数。

1. 0-1 背包（物品仅选 1 次）

• 问题：n 件物品，重量w[i]、价值v[i]，背包容量 C，选物品不超重，求最大价值。

• 状态定义：dp[j] = 容量为 j 的背包的最大价值（空间优化后，原二维dp[i][j]压缩为一维）。

• 递推逻辑：对每件物品，从容量 C 倒序遍历（避免重复选），若j≥w[i]，则dp[j] = max(dp[j], dp[j-w[i]]+v[i])。

• 公式：

(dp[j] = \max(dp[j], dp[j - w[i]] + v[i]) \quad (j从C倒序到w[i]))

• 实例：w=[2,3,4]，v=[3,4,5]，C=5，得dp[5]=7（选w=2和w=3）。

2. 完全背包（物品可选无限次）

• 差异：容量从w[i]正序遍历（允许重复选）。

• 公式：

(dp[j] = \max(dp[j], dp[j - w[i]] + v[i]) \quad (j从w[i]正序到C))

• 实例：w=[2,3]，v=[3,4]，C=5，得dp[5]=7（选w=2+3）。

3. 多重背包（物品选有限次）

• 差异：将物品数量k[i]拆分为二进制（如k=5拆为1+2+2），转化为 0-1 背包。

• 实例：w=[2]，v=[3]，k=3，C=5，拆分为1+2，得dp[5]=6（选2*2=4斤）。

四、树形 DP：基于树结构的后序递推

1. 核心逻辑

状态与 “树的节点及其子树” 绑定，递推顺序为 “后序遍历”（先算子树，再算父节点），适用于树结构的优化问题（如独立集、最长路径）。

2. 模型与公式（以树的最大独立集为例）

• 问题：树中选节点，无相邻节点，求最大节点数。

• 状态定义：

dp[u][1] = 选节点 u 时，u 的子树的最大独立集大小；

dp[u][0] = 不选 u 时，u 的子树的最大独立集大小。

• 递推逻辑：

• • 选 u：子节点必不选，dp[u][1] = 1 + sum(dp[v][0])（v 为 u 的子节点）；
• • 不选 u：子节点可选可不选，dp[u][0] = sum(max(dp[v][0], dp[v][1]))。

• 公式：

(\begin{cases} dp[u][1] = 1 + \sum_{v \in son(u)} dp[v][0] \ dp[u][0] = \sum_{v \in son(u)} \max(dp[v][0], dp[v][1]) \end{cases})

• 结果：max(dp[root][0], dp[root][1])（root 为树的根）

3. 实例

树结构root=1，子节点2、3；2的子节点4：

计算得dp[1][0]=2，dp[1][1]=2，最大独立集大小为 2。

五、状态压缩 DP：二进制表示状态的递推

1. 核心逻辑

用二进制数（mask）表示 “元素的选择状态”（如mask=101表示第 1、3 个元素已选），状态数为2^n（n≤20 时可行），适用于小规模集合选择问题。

2. 模型与公式（以旅行商问题 TSP 为例）

• 问题：n 个城市，距离d[i][j]，从城市 0 出发，遍历所有城市一次返回，求最短路径。

• 状态定义：dp[mask][u] = 已访问城市集合为 mask，当前在城市 u 的最短路径长度。

• 递推逻辑：对未访问城市 v（mask的第 v 位为 0），从 u 到 v，更新dp[mask|(1<<v)][v] = min(dp[mask|(1<<v)][v], dp[mask][u]+d[u][v])。

• 公式：

(dp[mask | (1<<v)][v] = \min_{v \notin mask} (dp[mask][u] + d[u][v]))

• 边界：dp[1<<0][0] = 0；结果：min(dp[(1<<n)-1][u] + d[u][0])

3. 实例

n=3，d=[[0,2,3],[2,0,1],[3,1,0]]：

计算得dp[111][1]+d[1][0] = 3+2=5，dp[111][2]+d[2][0] = 3+3=6，最短路径为 5。

六、数位 DP：基于数字位数的递推

1. 核心逻辑

按数字的 “个位、十位、百位” 等位数拆分问题，记录 “前导零、是否受限（是否达到当前位的最大值）” 等状态，适用于 “统计区间内满足特定条件的数字个数”。

2. 模型与公式（以统计 1~X 中含数字 3 的数的个数为例）

• 问题：统计 1 到 X（如 X=100）中，数字包含至少一个 3 的数的个数。

• 状态定义：dp[pos][has3][limit] = 处理到第 pos 位，是否已含 3（has3=0/1），是否受当前位最大值限制（limit=0/1）时，满足条件的数的个数。

• 递推逻辑：

• • 确定当前位的最大可取数字 up（若 limit=1，则 up=X 的第 pos 位；否则 up=9）；
• • 遍历当前位可取数字 d（0~up），更新 has3（d=3 则 has3=1）和 limit（d=up 且原 limit=1 则 limit=1），累加子状态个数。

• 公式：

(dp[pos][has3][limit] = \sum_{d=0}^{up} dp[pos-1][has3 | (d3)][limit & (dup)])

• 边界：pos=0 时，若 has3=1 则返回 1，否则返回 0；结果：dp[len(X)][0][1]（从最高位开始，初始无 3、受限）

3. 实例

X=100：

计算得 1~100 中含 3 的数共 20 个（3,13,...,93 共 10 个；30~39 共 10 个）。

七、计数型 DP：统计可行方案数的递推

1. 核心逻辑

状态表示 “达到特定条件的方案数”，递推时累加所有可行子方案的数量，适用于 “计数类问题”（如凑数、路径数）。

2. 模型与公式（以用 1、2、5 角凑 n 角的方案数为例）

• 问题：用 1 角、2 角、5 角硬币凑 n 角，求不同方案数（顺序无关）。

• 状态定义：dp[j] = 凑 j 角的方案数。

• 递推逻辑：依次考虑每种硬币，对容量 j 从硬币面值到 n 遍历，累加 “加入当前硬币后的方案数”。

• 公式：

(dp[j] += dp[j - coin] \quad (coin为当前硬币面值，j从coin到n))

• 边界：dp[0] = 1（凑 0 角有 1 种方案：不选任何硬币）；结果：dp[n]

3. 实例

n=5 角：

计算得dp[5] = 4（1+1+1+1+1；1+1+1+2；1+2+2；5）。

八、递推型 DP：基于递推关系的基础 DP

1. 核心逻辑

最基础的 DP 类型，状态直接依赖前序固定数量的状态，递推关系明确，无复杂约束（如斐波那契数列、爬楼梯）。

2. 模型与公式（以爬楼梯为例）

• 问题：楼梯有 n 级，每次走 1 或 2 级，求到楼顶的走法数。

• 状态定义：dp[i] = 到第 i 级的走法数。

• 递推逻辑：到第 i 级可从 i-1 级走 1 级，或从 i-2 级走 2 级，方案数累加。

• 公式：

(dp[i] = dp[i-1] + dp[i-2])

• 边界：dp[1] = 1，dp[2] = 2；结果：dp[n]

3. 实例

n=5：

dp[3]=3，dp[4]=5，dp[5]=8，共 8 种走法。

九、概率型 DP：基于概率的期望 / 概率递推

1. 核心逻辑

状态表示 “达到特定条件的概率或期望”，递推时结合概率公式（如期望线性性质），适用于随机事件的概率 / 期望计算。

2. 模型与公式（以骰子游戏期望为例）

• 问题：掷骰子，若掷出 1 则结束，否则继续掷，求掷骰子的期望次数。

• 状态定义：E = 从当前状态到结束的期望次数。

• 递推逻辑：掷出 1 的概率为 1/6（结束，次数 1），掷出 2~6 的概率为 5/6（继续，次数 1+E），按期望公式计算。

• 公式：

(E = \frac{1}{6} \times 1 + \frac{5}{6} \times (1 + E))

• 求解：化简得E = 6；结果：期望次数为 6。

3. 实例

上述问题直接求解得期望为 6，即平均掷 6 次结束。

十、博弈型 DP：基于博弈规则的胜负递推

1. 核心逻辑

状态表示 “当前局面下先手的胜负状态”（如必胜 / 必败），递推时根据博弈规则（如可移动的步数、可选的操作），判断是否存在让对手进入必败态的操作。

2. 模型与公式（以尼姆游戏为例）

• 问题：n 堆石子，两人轮流取任意堆的任意石子，取最后一颗者胜，判断先手是否必胜。

• 状态定义：xor_sum = 所有堆石子数的异或值。

• 递推逻辑：若xor_sum != 0，先手可通过取石子使异或值变为 0（对手进入必败态）；若xor_sum == 0，无论怎么取，异或值都会变为非 0（先手必败）。

• 公式：

先手必胜 (\iff) (\text{xor_sum} = a_1 \oplus a_2 \oplus ... \oplus a_n \neq 0)

• 结果：根据异或和判断胜负。

3. 实例

石子堆[3,4,5]：

3^4=7，7^5=2≠0，先手必胜。

十一、记忆化搜索：递归 + 缓存的 DP 实现

1. 核心逻辑

记忆化搜索是动态规划的 “递归实现形式”，核心思路是：用递归拆解问题为子问题，用缓存（数组、哈希表等）存储已计算的子问题结果，避免重复递归计算（解决递归的 “重叠子问题” 问题）。其本质与迭代式 DP 一致，只是实现方式不同 —— 迭代式 DP 是 “从子问题推原问题”，记忆化搜索是 “从原问题拆子问题”，更适用于递归关系清晰、状态依赖复杂（如不规则依赖）的场景。

2. 模型与公式（以斐波那契数列的记忆化搜索为例）

• 问题：求斐波那契数列第 n 项，已知递推关系：f(1)=1，f(2)=1，f(n)=f(n-1)+f(n-2)（n≥3）。

• 状态定义：

函数dfs(n)表示 “求第 n 项斐波那契数”；

缓存数组memo，memo[i]存储已计算的f(i)，初始值为-1（标记未计算）。

• 递归逻辑：

1. 1. 若n≤2，直接返回 1（ base case，无需递归）；
2. 1. 若memo[n]≠-1，说明已计算过，直接返回memo[n]（复用结果，避免重复递归）；
3. 1. 若未计算，递归计算f(n-1)和f(n-2)，求和后存入memo[n]，再返回结果（缓存子问题解）。

• 完整公式：

(dfs(n) = \begin{cases} 1 & n \leq 2 \ memo[n] & memo[n] \neq -1 \ memo[n] = dfs(n-1) + dfs(n-2) & 其他情况 \end{cases})

• 结果：调用dfs(n)，返回值即为第 n 项斐波那契数。

3. 模型构建步骤

记忆化搜索的通用实现步骤可总结为以下 4 步，适用于各类问题：

步骤	操作要点	示例（斐波那契数列）
1	定义递归函数	定义dfs(n)：输入 “问题规模 n”，输出 “第 n 项结果”
2	确定 base case	当n≤2时，直接返回 1（最小子问题，无需拆分）
3	设计缓存结构	初始化数组memo，大小为n+1，初始值-1（标记未计算）
4	实现递归与缓存	先检查缓存，再递归计算，最后存储结果到缓存

4. 典型例题（进阶：数字三角形的记忆化搜索）

例题描述

给定一个 n 行的数字三角形，从顶部出发，每次只能向下或向右下走，求到达底部的路径最大和（如下图，n=4 时，最大路径和为3+7+4+9=23）：

    3
   7 4
  2 4 6
 8 5 9 3

解题过程

• 步骤 1：定义递归函数

设dfs(i,j)表示 “从第 i 行第 j 列（下标从 0 开始）出发，到达底部的最大路径和”，目标是求dfs(0,0)。

• 步骤 2：确定 base case

当i == n-1（到达最后一行）时，路径和就是当前数字，即dfs(i,j) = triangle[i][j]。

• 步骤 3：设计缓存结构

初始化二维数组memo，大小为n×n，初始值-1（数字三角形每行 j 的范围是 0~i，未使用的位置不影响）。

• 步骤 4：实现递归与缓存

若memo[i][j]≠-1，直接返回；否则，递归计算 “向下走”（dfs(i+1,j)）和 “向右下走”（dfs(i+1,j+1)）的最大路径和，加上当前数字后存入缓存：

(dfs(i,j) = triangle[i][j] + \max(dfs(i+1,j), dfs(i+1,j+1)))

计算结果

以示例三角形为例：

• dfs(3,0)=8，dfs(3,1)=5，dfs(3,2)=9，dfs(3,3)=3（base case）；

• dfs(2,0)=2 + max(8,5)=10，dfs(2,1)=4 + max(5,9)=13，dfs(2,2)=6 + max(9,3)=15；

• dfs(1,0)=7 + max(10,13)=20，dfs(1,1)=4 + max(13,15)=19；

• dfs(0,0)=3 + max(20,19)=23，即最大路径和为 23。

5. 记忆化搜索与迭代式 DP 的对比

维度	记忆化搜索（递归）	迭代式 DP（递推）
实现思路	自顶向下（原问题→子问题）	自底向上（子问题→原问题）
代码复杂度	递归逻辑清晰，无需手动规划递推顺序	需明确递推顺序（如线性、区间长度）
空间开销	额外消耗递归栈空间（需避免栈溢出）	仅需缓存数组空间
适用场景	状态依赖不规则（如树形、图结构）	状态依赖规则（如线性、区间）

通过对比可知，记忆化搜索更适合 “子问题依赖关系不规律” 的场景（如树形问题、图的路径问题），而迭代式 DP 更适合 “子问题按固定顺序排列” 的场景（如线性、区间问题），二者可根据问题特点灵活选择。

总结：11 种 DP 类型的核心区别与适用场景

DP 类型	核心特征	典型问题	关键技巧
线性 DP	状态与线性序列绑定	最长上升子序列、最大子数组和	按序列顺序递推
区间 DP	状态与区间[l,r]绑定	石子合并、回文子串计数	按区间长度递增递推
背包 DP	资源约束下的选择优化	0-1 背包、完全背包、多重背包	空间优化（一维数组）、二进制拆分
树形 DP	状态与树节点 + 子树绑定	树的最大独立集、树上最长路径	后序遍历（先算子树，再算父节点）
状态压缩 DP	二进制 mask 表示状态	旅行商问题（TSP）、集合覆盖	状态二进制表示（n≤20）
数位 DP	按数字位数拆分问题	统计区间内含特定数字的数	记录 “前导零、是否受限” 状态
计数型 DP	统计可行方案数	硬币凑数、路径计数	累加子方案数（边界dp[0]=1）
递推型 DP	基础递推关系（固定依赖）	爬楼梯、斐波那契数列	明确 base case 和递推公式
概率型 DP	状态表示概率 / 期望	骰子游戏期望、抽奖概率	结合概率公式（期望线性性质）
博弈型 DP	状态表示博弈胜负（必胜 / 必败）	尼姆游戏、取石子游戏	判断是否存在 “让对手必败” 的操作
记忆化搜索	递归 + 缓存（DP 的递归实现）	数字三角形、迷宫路径最大和	缓存子问题结果，避免重复递归

掌握 11 种 DP 类型的核心逻辑后，解题的关键在于：根据问题特征判断 DP 类型→定义合理的状态→推导递推公式→处理边界条件。通过典型例题的练习，可逐步建立 DP 思维，高效解决复杂问题。