14.1 初探动态规划¶
动态规划(dynamic programming)是一个重要的算法范式,它将一个问题分解为一系列更小的子问题,并通过存储子问题的解来避免重复计算,从而大幅提升时间效率。
在本节中,我们从一个经典例题入手,先给出它的暴力回溯解法,观察其中包含的重叠子问题,再逐步导出更高效的动态规划解法。
爬楼梯
给定一个共有 \(n\) 阶的楼梯,你每步可以上 \(1\) 阶或者 \(2\) 阶,请问有多少种方案可以爬到楼顶?
如图 14-1 所示,对于一个 \(3\) 阶楼梯,共有 \(3\) 种方案可以爬到楼顶。
图 14-1 爬到第 3 阶的方案数量
图解 14-1:爬到第三阶的三种方案
三条台阶轨迹展示爬到第 3 阶的不同走法。
设地面起点编号为 0,每一步可以选择向上爬 1 阶或 2 阶,目标是恰好爬上第 3 阶楼梯。
楼梯的台阶编号从左到右为 0 至 6,目标第 3 阶的踏面以绿色高亮。三组跳跃弧线都画在同一段楼梯上方,弧线与下方的台阶序列一一对应;图下注明“爬上第 3 阶楼梯共有 3 种方案”。
青色实线方案按台阶编号 0→1→2→3 前进,即连续三次各上 1 阶;蓝色点线方案按 0→2→3 前进,即先上 2 阶到第 2 阶、再上 1 阶到第 3 阶;橙色虚线方案按 0→1→3 前进,即先上 1 阶到第 1 阶、再上 2 阶到第 3 阶。先上 2 阶再上 1 阶与先上 1 阶再上 2 阶经过不同台阶,计为不同方案。
本题的目标是求解方案数量,我们可以考虑通过回溯来穷举所有可能性。具体来说,将爬楼梯想象为一个多轮选择的过程:从地面出发,每轮选择上 \(1\) 阶或 \(2\) 阶,每当到达楼梯顶部时就将方案数量加 \(1\) ,当越过楼梯顶部时就将其剪枝。代码如下所示:
def backtrack(choices: list[int], state: int, n: int, res: list[int]) -> int:
"""回溯"""
# 当爬到第 n 阶时,方案数量加 1
if state == n:
res[0] += 1
# 遍历所有选择
for choice in choices:
# 剪枝:不允许越过第 n 阶
if state + choice > n:
continue
# 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res)
# 回退
def climbing_stairs_backtrack(n: int) -> int:
"""爬楼梯:回溯"""
choices = [1, 2] # 可选择向上爬 1 阶或 2 阶
state = 0 # 从第 0 阶开始爬
res = [0] # 使用 res[0] 记录方案数量
backtrack(choices, state, n, res)
return res[0]
/* 回溯 */
void backtrack(vector<int> &choices, int state, int n, vector<int> &res) {
// 当爬到第 n 阶时,方案数量加 1
if (state == n)
res[0]++;
// 遍历所有选择
for (auto &choice : choices) {
// 剪枝:不允许越过第 n 阶
if (state + choice > n)
continue;
// 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res);
// 回退
}
}
/* 爬楼梯:回溯 */
int climbingStairsBacktrack(int n) {
vector<int> choices = {1, 2}; // 可选择向上爬 1 阶或 2 阶
int state = 0; // 从第 0 阶开始爬
vector<int> res = {0}; // 使用 res[0] 记录方案数量
backtrack(choices, state, n, res);
return res[0];
}
/* 回溯 */
void backtrack(List<Integer> choices, int state, int n, List<Integer> res) {
// 当爬到第 n 阶时,方案数量加 1
if (state == n)
res.set(0, res.get(0) + 1);
// 遍历所有选择
for (Integer choice : choices) {
// 剪枝:不允许越过第 n 阶
if (state + choice > n)
continue;
// 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res);
// 回退
}
}
/* 爬楼梯:回溯 */
int climbingStairsBacktrack(int n) {
List<Integer> choices = Arrays.asList(1, 2); // 可选择向上爬 1 阶或 2 阶
int state = 0; // 从第 0 阶开始爬
List<Integer> res = new ArrayList<>();
res.add(0); // 使用 res[0] 记录方案数量
backtrack(choices, state, n, res);
return res.get(0);
}
/* 回溯 */
void Backtrack(List<int> choices, int state, int n, List<int> res) {
// 当爬到第 n 阶时,方案数量加 1
if (state == n)
res[0]++;
// 遍历所有选择
foreach (int choice in choices) {
// 剪枝:不允许越过第 n 阶
if (state + choice > n)
continue;
// 尝试:做出选择,更新状态
Backtrack(choices, state + choice, n, res);
// 回退
}
}
/* 爬楼梯:回溯 */
int ClimbingStairsBacktrack(int n) {
List<int> choices = [1, 2]; // 可选择向上爬 1 阶或 2 阶
int state = 0; // 从第 0 阶开始爬
List<int> res = [0]; // 使用 res[0] 记录方案数量
Backtrack(choices, state, n, res);
return res[0];
}
/* 回溯 */
func backtrack(choices []int, state, n int, res []int) {
// 当爬到第 n 阶时,方案数量加 1
if state == n {
res[0] = res[0] + 1
}
// 遍历所有选择
for _, choice := range choices {
// 剪枝:不允许越过第 n 阶
if state+choice > n {
continue
}
// 尝试:做出选择,更新状态
backtrack(choices, state+choice, n, res)
// 回退
}
}
/* 爬楼梯:回溯 */
func climbingStairsBacktrack(n int) int {
// 可选择向上爬 1 阶或 2 阶
choices := []int{1, 2}
// 从第 0 阶开始爬
state := 0
res := make([]int, 1)
// 使用 res[0] 记录方案数量
res[0] = 0
backtrack(choices, state, n, res)
return res[0]
}
/* 回溯 */
func backtrack(choices: [Int], state: Int, n: Int, res: inout [Int]) {
// 当爬到第 n 阶时,方案数量加 1
if state == n {
res[0] += 1
}
// 遍历所有选择
for choice in choices {
// 剪枝:不允许越过第 n 阶
if state + choice > n {
continue
}
// 尝试:做出选择,更新状态
backtrack(choices: choices, state: state + choice, n: n, res: &res)
// 回退
}
}
/* 爬楼梯:回溯 */
func climbingStairsBacktrack(n: Int) -> Int {
let choices = [1, 2] // 可选择向上爬 1 阶或 2 阶
let state = 0 // 从第 0 阶开始爬
var res: [Int] = []
res.append(0) // 使用 res[0] 记录方案数量
backtrack(choices: choices, state: state, n: n, res: &res)
return res[0]
}
/* 回溯 */
function backtrack(choices, state, n, res) {
// 当爬到第 n 阶时,方案数量加 1
if (state === n) res.set(0, res.get(0) + 1);
// 遍历所有选择
for (const choice of choices) {
// 剪枝:不允许越过第 n 阶
if (state + choice > n) continue;
// 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res);
// 回退
}
}
/* 爬楼梯:回溯 */
function climbingStairsBacktrack(n) {
const choices = [1, 2]; // 可选择向上爬 1 阶或 2 阶
const state = 0; // 从第 0 阶开始爬
const res = new Map();
res.set(0, 0); // 使用 res[0] 记录方案数量
backtrack(choices, state, n, res);
return res.get(0);
}
/* 回溯 */
function backtrack(
choices: number[],
state: number,
n: number,
res: Map<0, any>
): void {
// 当爬到第 n 阶时,方案数量加 1
if (state === n) res.set(0, res.get(0) + 1);
// 遍历所有选择
for (const choice of choices) {
// 剪枝:不允许越过第 n 阶
if (state + choice > n) continue;
// 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res);
// 回退
}
}
/* 爬楼梯:回溯 */
function climbingStairsBacktrack(n: number): number {
const choices = [1, 2]; // 可选择向上爬 1 阶或 2 阶
const state = 0; // 从第 0 阶开始爬
const res = new Map();
res.set(0, 0); // 使用 res[0] 记录方案数量
backtrack(choices, state, n, res);
return res.get(0);
}
/* 回溯 */
void backtrack(List<int> choices, int state, int n, List<int> res) {
// 当爬到第 n 阶时,方案数量加 1
if (state == n) {
res[0]++;
}
// 遍历所有选择
for (int choice in choices) {
// 剪枝:不允许越过第 n 阶
if (state + choice > n) continue;
// 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res);
// 回退
}
}
/* 爬楼梯:回溯 */
int climbingStairsBacktrack(int n) {
List<int> choices = [1, 2]; // 可选择向上爬 1 阶或 2 阶
int state = 0; // 从第 0 阶开始爬
List<int> res = [];
res.add(0); // 使用 res[0] 记录方案数量
backtrack(choices, state, n, res);
return res[0];
}
/* 回溯 */
fn backtrack(choices: &[i32], state: i32, n: i32, res: &mut [i32]) {
// 当爬到第 n 阶时,方案数量加 1
if state == n {
res[0] = res[0] + 1;
}
// 遍历所有选择
for &choice in choices {
// 剪枝:不允许越过第 n 阶
if state + choice > n {
continue;
}
// 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res);
// 回退
}
}
/* 爬楼梯:回溯 */
fn climbing_stairs_backtrack(n: usize) -> i32 {
let choices = vec![1, 2]; // 可选择向上爬 1 阶或 2 阶
let state = 0; // 从第 0 阶开始爬
let mut res = Vec::new();
res.push(0); // 使用 res[0] 记录方案数量
backtrack(&choices, state, n as i32, &mut res);
res[0]
}
/* 回溯 */
void backtrack(int *choices, int state, int n, int *res, int len) {
// 当爬到第 n 阶时,方案数量加 1
if (state == n)
res[0]++;
// 遍历所有选择
for (int i = 0; i < len; i++) {
int choice = choices[i];
// 剪枝:不允许越过第 n 阶
if (state + choice > n)
continue;
// 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res, len);
// 回退
}
}
/* 爬楼梯:回溯 */
int climbingStairsBacktrack(int n) {
int choices[2] = {1, 2}; // 可选择向上爬 1 阶或 2 阶
int state = 0; // 从第 0 阶开始爬
int *res = (int *)malloc(sizeof(int));
*res = 0; // 使用 res[0] 记录方案数量
int len = sizeof(choices) / sizeof(int);
backtrack(choices, state, n, res, len);
int result = *res;
free(res);
return result;
}
/* 回溯 */
fun backtrack(
choices: MutableList<Int>,
state: Int,
n: Int,
res: MutableList<Int>
) {
// 当爬到第 n 阶时,方案数量加 1
if (state == n)
res[0] = res[0] + 1
// 遍历所有选择
for (choice in choices) {
// 剪枝:不允许越过第 n 阶
if (state + choice > n) continue
// 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res)
// 回退
}
}
/* 爬楼梯:回溯 */
fun climbingStairsBacktrack(n: Int): Int {
val choices = mutableListOf(1, 2) // 可选择向上爬 1 阶或 2 阶
val state = 0 // 从第 0 阶开始爬
val res = mutableListOf<Int>()
res.add(0) // 使用 res[0] 记录方案数量
backtrack(choices, state, n, res)
return res[0]
}
### 回溯 ###
def backtrack(choices, state, n, res)
# 当爬到第 n 阶时,方案数量加 1
res[0] += 1 if state == n
# 遍历所有选择
for choice in choices
# 剪枝:不允许越过第 n 阶
next if state + choice > n
# 尝试:做出选择,更新状态
backtrack(choices, state + choice, n, res)
end
# 回退
end
### 爬楼梯:回溯 ###
def climbing_stairs_backtrack(n)
choices = [1, 2] # 可选择向上爬 1 阶或 2 阶
state = 0 # 从第 0 阶开始爬
res = [0] # 使用 res[0] 记录方案数量
backtrack(choices, state, n, res)
res.first
end
可视化运行
14.1.1 方法一:暴力搜索¶
回溯算法通常并不显式地对问题进行拆解,而是将求解问题看作一系列决策步骤,通过试探和剪枝,搜索所有可能的解。
我们可以尝试从问题分解的角度分析这道题。设爬到第 \(i\) 阶共有 \(dp[i]\) 种方案,那么 \(dp[i]\) 就是原问题,其子问题包括:
由于每轮只能上 \(1\) 阶或 \(2\) 阶,因此当我们站在第 \(i\) 阶楼梯上时,上一轮只可能站在第 \(i - 1\) 阶或第 \(i - 2\) 阶上。换句话说,我们只能从第 \(i -1\) 阶或第 \(i - 2\) 阶迈向第 \(i\) 阶。
由此便可得出一个重要推论:爬到第 \(i - 1\) 阶的方案数加上爬到第 \(i - 2\) 阶的方案数就等于爬到第 \(i\) 阶的方案数。公式如下:
这意味着在爬楼梯问题中,各个子问题之间存在递推关系,原问题的解可以由子问题的解构建得来。图 14-2 展示了该递推关系。
图 14-2 方案数量递推关系
图解 14-2:第五阶的方案由第三、四阶相加
到达第 5 阶的最后一步只能来自第 3 阶或第 4 阶,因此方案数为 3+5=8。
每一步只能上 1 阶或 2 阶,记 dp[n] 为爬到第 n 阶楼梯的方案数,其中初始状态为 dp[1]=1、dp[2]=2。
楼梯上第 3、第 4、第 5 阶分别用绿色、青色和蓝色突出显示。3 条绿色虚线汇入第 3 阶(标有 dp[3]=3),5 条青色实线汇入第 4 阶(标有 dp[4]=5),随后分别经一条跨 2 阶的绿色虚线和一条跨 1 阶的青色实线汇入第 5 阶;顶部写出 dp[5]=dp[3]+dp[4]=8,底部对照列出阶数 1 至 6 与对应的方案数。
| 阶数 n | 方案数 dp[n] |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
| 6 | 13 |
要爬到第 5 阶,最后一步要么是从第 3 阶向上跳 2 阶,要么是从第 4 阶向上跳 1 阶。把到达第 3 阶的 3 种走法各接上一次 2 阶跳跃,就得到 3 种到达第 5 阶的走法;把到达第 4 阶的 5 种走法各接上一次 1 阶跳跃,又得到另外 5 种走法。这两类走法的最后一步的来源阶不同,彼此不重不漏,所以 dp[5]=dp[3]+dp[4]=3+5=8。推广到任意第 i 阶(i≥3),都有 dp[i]=dp[i-1]+dp[i-2]。
我们可以根据递推公式得到暴力搜索解法。以 \(dp[n]\) 为起始点,递归地将一个较大问题拆解为两个较小问题的和,直至到达最小子问题 \(dp[1]\) 和 \(dp[2]\) 时返回。其中,最小子问题的解是已知的,即 \(dp[1] = 1\)、\(dp[2] = 2\) ,表示爬到第 \(1\)、\(2\) 阶分别有 \(1\)、\(2\) 种方案。
观察以下代码,它和标准回溯代码都属于深度优先搜索,但更加简洁:
可视化运行
图 14-3 展示了暴力搜索形成的递归树。对于问题 \(dp[n]\) ,其递归树的深度为 \(n\) ,时间复杂度为 \(O(2^n)\) 。指数阶属于爆炸式增长,如果我们输入一个比较大的 \(n\) ,则会陷入漫长的等待之中。
图 14-3 爬楼梯对应递归树
图解 14-3:暴力爬楼梯搜索的重叠子问题
从 dp[9] 自顶向下暴力递归拆分时,相同的子问题不共享结果,会在不同分支中被反复展开求解。
爬楼梯问题中每步上 1 阶或 2 阶,dp[i] 表示爬到第 i 阶的方案数。暴力搜索直接按递推式 dp[i] = dp[i − 1] + dp[i − 2] 向下递归分解,直到触及基本情况 dp[1] = 1 或 dp[2] = 2。
求 dp[9] 时先求 dp[8] 与 dp[7];求 dp[8] 又会求 dp[7] 与 dp[6]。暴力树中的两个 dp[7] 不共享一次计算,每次遇到都会各自再次展开求解。
图中只画到前四层共 15 个状态节点,底部 16 个省略号表示继续递归至基本情况 dp[1] 或 dp[2]。表中次数(如 dp[5] 出现 4 次)只统计已画出的四层,不代表整个递归过程的总次数。
下表先列画出的四层,再按状态汇总。分解表的左右子问题按递推式列出;第 4 层各节点的子问题在图中均以省略号表示,并未逐个画出。其中 dp[4]、dp[3] 只出现在第 4 层,分解表中这两行的子问题均由递推式推出,图中未画出。
| 层(根为第 1 层) | 状态(从左到右) |
|---|---|
| 1 | dp[9] |
| 2 | dp[8]、dp[7] |
| 3 | dp[7]、dp[6]、dp[6]、dp[5] |
| 4 | dp[6]、dp[5]、dp[5]、dp[4]、dp[5]、dp[4]、dp[4]、dp[3] |
| 状态 | 左子问题 | 右子问题 | 前四层出现次数 |
|---|---|---|---|
| dp[9] | dp[8] | dp[7] | 1 |
| dp[8] | dp[7] | dp[6] | 1 |
| dp[7] | dp[6] | dp[5] | 2 |
| dp[6] | dp[5] | dp[4] | 3 |
| dp[5] | dp[4] | dp[3] | 4 |
| dp[4] | dp[3] | dp[2] | 3 |
| dp[3] | dp[2] | dp[1] | 1 |
图底文字将重叠子问题与指数级耗时联系起来:暴力递归反复求解同一状态,时间复杂度为 O(2^n)。
观察图 14-3 ,指数阶的时间复杂度是“重叠子问题”导致的。例如 \(dp[9]\) 被分解为 \(dp[8]\) 和 \(dp[7]\) ,\(dp[8]\) 被分解为 \(dp[7]\) 和 \(dp[6]\) ,两者都包含子问题 \(dp[7]\) 。
以此类推,子问题中包含更小的重叠子问题,子子孙孙无穷尽也。绝大部分计算资源都浪费在这些重叠的子问题上。
14.1.2 方法二:记忆化搜索¶
为了提升算法效率,我们希望所有的重叠子问题都只被计算一次。为此,我们声明一个数组 mem 来记录每个子问题的解,并在搜索过程中将重叠子问题剪枝。
- 当首次计算 \(dp[i]\) 时,我们将其记录至
mem[i],以便之后使用。 - 当再次需要计算 \(dp[i]\) 时,我们便可直接从
mem[i]中获取结果,从而避免重复计算该子问题。
代码如下所示:
def dfs(i: int, mem: list[int]) -> int:
"""记忆化搜索"""
# 已知 dp[1] 和 dp[2] ,返回之
if i == 1 or i == 2:
return i
# 若存在记录 dp[i] ,则直接返回之
if mem[i] != -1:
return mem[i]
# dp[i] = dp[i-1] + dp[i-2]
count = dfs(i - 1, mem) + dfs(i - 2, mem)
# 记录 dp[i]
mem[i] = count
return count
def climbing_stairs_dfs_mem(n: int) -> int:
"""爬楼梯:记忆化搜索"""
# mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
mem = [-1] * (n + 1)
return dfs(n, mem)
/* 记忆化搜索 */
int dfs(int i, vector<int> &mem) {
// 已知 dp[1] 和 dp[2] ,返回之
if (i == 1 || i == 2)
return i;
// 若存在记录 dp[i] ,则直接返回之
if (mem[i] != -1)
return mem[i];
// dp[i] = dp[i-1] + dp[i-2]
int count = dfs(i - 1, mem) + dfs(i - 2, mem);
// 记录 dp[i]
mem[i] = count;
return count;
}
/* 爬楼梯:记忆化搜索 */
int climbingStairsDFSMem(int n) {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
vector<int> mem(n + 1, -1);
return dfs(n, mem);
}
/* 记忆化搜索 */
int dfs(int i, int[] mem) {
// 已知 dp[1] 和 dp[2] ,返回之
if (i == 1 || i == 2)
return i;
// 若存在记录 dp[i] ,则直接返回之
if (mem[i] != -1)
return mem[i];
// dp[i] = dp[i-1] + dp[i-2]
int count = dfs(i - 1, mem) + dfs(i - 2, mem);
// 记录 dp[i]
mem[i] = count;
return count;
}
/* 爬楼梯:记忆化搜索 */
int climbingStairsDFSMem(int n) {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
int[] mem = new int[n + 1];
Arrays.fill(mem, -1);
return dfs(n, mem);
}
/* 记忆化搜索 */
int DFS(int i, int[] mem) {
// 已知 dp[1] 和 dp[2] ,返回之
if (i == 1 || i == 2)
return i;
// 若存在记录 dp[i] ,则直接返回之
if (mem[i] != -1)
return mem[i];
// dp[i] = dp[i-1] + dp[i-2]
int count = DFS(i - 1, mem) + DFS(i - 2, mem);
// 记录 dp[i]
mem[i] = count;
return count;
}
/* 爬楼梯:记忆化搜索 */
int ClimbingStairsDFSMem(int n) {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
int[] mem = new int[n + 1];
Array.Fill(mem, -1);
return DFS(n, mem);
}
/* 记忆化搜索 */
func dfsMem(i int, mem []int) int {
// 已知 dp[1] 和 dp[2] ,返回之
if i == 1 || i == 2 {
return i
}
// 若存在记录 dp[i] ,则直接返回之
if mem[i] != -1 {
return mem[i]
}
// dp[i] = dp[i-1] + dp[i-2]
count := dfsMem(i-1, mem) + dfsMem(i-2, mem)
// 记录 dp[i]
mem[i] = count
return count
}
/* 爬楼梯:记忆化搜索 */
func climbingStairsDFSMem(n int) int {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
mem := make([]int, n+1)
for i := range mem {
mem[i] = -1
}
return dfsMem(n, mem)
}
/* 记忆化搜索 */
func dfs(i: Int, mem: inout [Int]) -> Int {
// 已知 dp[1] 和 dp[2] ,返回之
if i == 1 || i == 2 {
return i
}
// 若存在记录 dp[i] ,则直接返回之
if mem[i] != -1 {
return mem[i]
}
// dp[i] = dp[i-1] + dp[i-2]
let count = dfs(i: i - 1, mem: &mem) + dfs(i: i - 2, mem: &mem)
// 记录 dp[i]
mem[i] = count
return count
}
/* 爬楼梯:记忆化搜索 */
func climbingStairsDFSMem(n: Int) -> Int {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
var mem = Array(repeating: -1, count: n + 1)
return dfs(i: n, mem: &mem)
}
/* 记忆化搜索 */
function dfs(i, mem) {
// 已知 dp[1] 和 dp[2] ,返回之
if (i === 1 || i === 2) return i;
// 若存在记录 dp[i] ,则直接返回之
if (mem[i] != -1) return mem[i];
// dp[i] = dp[i-1] + dp[i-2]
const count = dfs(i - 1, mem) + dfs(i - 2, mem);
// 记录 dp[i]
mem[i] = count;
return count;
}
/* 爬楼梯:记忆化搜索 */
function climbingStairsDFSMem(n) {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
const mem = new Array(n + 1).fill(-1);
return dfs(n, mem);
}
/* 记忆化搜索 */
function dfs(i: number, mem: number[]): number {
// 已知 dp[1] 和 dp[2] ,返回之
if (i === 1 || i === 2) return i;
// 若存在记录 dp[i] ,则直接返回之
if (mem[i] != -1) return mem[i];
// dp[i] = dp[i-1] + dp[i-2]
const count = dfs(i - 1, mem) + dfs(i - 2, mem);
// 记录 dp[i]
mem[i] = count;
return count;
}
/* 爬楼梯:记忆化搜索 */
function climbingStairsDFSMem(n: number): number {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
const mem = new Array(n + 1).fill(-1);
return dfs(n, mem);
}
/* 记忆化搜索 */
int dfs(int i, List<int> mem) {
// 已知 dp[1] 和 dp[2] ,返回之
if (i == 1 || i == 2) return i;
// 若存在记录 dp[i] ,则直接返回之
if (mem[i] != -1) return mem[i];
// dp[i] = dp[i-1] + dp[i-2]
int count = dfs(i - 1, mem) + dfs(i - 2, mem);
// 记录 dp[i]
mem[i] = count;
return count;
}
/* 爬楼梯:记忆化搜索 */
int climbingStairsDFSMem(int n) {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
List<int> mem = List.filled(n + 1, -1);
return dfs(n, mem);
}
/* 记忆化搜索 */
fn dfs(i: usize, mem: &mut [i32]) -> i32 {
// 已知 dp[1] 和 dp[2] ,返回之
if i == 1 || i == 2 {
return i as i32;
}
// 若存在记录 dp[i] ,则直接返回之
if mem[i] != -1 {
return mem[i];
}
// dp[i] = dp[i-1] + dp[i-2]
let count = dfs(i - 1, mem) + dfs(i - 2, mem);
// 记录 dp[i]
mem[i] = count;
count
}
/* 爬楼梯:记忆化搜索 */
fn climbing_stairs_dfs_mem(n: usize) -> i32 {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
let mut mem = vec![-1; n + 1];
dfs(n, &mut mem)
}
/* 记忆化搜索 */
int dfs(int i, int *mem) {
// 已知 dp[1] 和 dp[2] ,返回之
if (i == 1 || i == 2)
return i;
// 若存在记录 dp[i] ,则直接返回之
if (mem[i] != -1)
return mem[i];
// dp[i] = dp[i-1] + dp[i-2]
int count = dfs(i - 1, mem) + dfs(i - 2, mem);
// 记录 dp[i]
mem[i] = count;
return count;
}
/* 爬楼梯:记忆化搜索 */
int climbingStairsDFSMem(int n) {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
int *mem = (int *)malloc((n + 1) * sizeof(int));
for (int i = 0; i <= n; i++) {
mem[i] = -1;
}
int result = dfs(n, mem);
free(mem);
return result;
}
/* 记忆化搜索 */
fun dfs(i: Int, mem: IntArray): Int {
// 已知 dp[1] 和 dp[2] ,返回之
if (i == 1 || i == 2) return i
// 若存在记录 dp[i] ,则直接返回之
if (mem[i] != -1) return mem[i]
// dp[i] = dp[i-1] + dp[i-2]
val count = dfs(i - 1, mem) + dfs(i - 2, mem)
// 记录 dp[i]
mem[i] = count
return count
}
/* 爬楼梯:记忆化搜索 */
fun climbingStairsDFSMem(n: Int): Int {
// mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
val mem = IntArray(n + 1)
mem.fill(-1)
return dfs(n, mem)
}
### 记忆化搜索 ###
def dfs(i, mem)
# 已知 dp[1] 和 dp[2] ,返回之
return i if i == 1 || i == 2
# 若存在记录 dp[i] ,则直接返回之
return mem[i] if mem[i] != -1
# dp[i] = dp[i-1] + dp[i-2]
count = dfs(i - 1, mem) + dfs(i - 2, mem)
# 记录 dp[i]
mem[i] = count
end
### 爬楼梯:记忆化搜索 ###
def climbing_stairs_dfs_mem(n)
# mem[i] 记录爬到第 i 阶的方案总数,-1 代表无记录
mem = Array.new(n + 1, -1)
dfs(n, mem)
end
可视化运行
观察图 14-4 ,经过记忆化处理后,所有重叠子问题都只需计算一次,时间复杂度优化至 \(O(n)\) ,这是一个巨大的飞跃。
图 14-4 记忆化搜索对应递归树
图解 14-4:记忆化搜索复用已算出的状态
沿左侧主链首次计算并缓存各子问题,右侧再次遇到相同状态时直接读取缓存返回并参与父状态求和。
仍求解每步上 1 阶或 2 阶的爬楼梯方案数,基本情况为 dp[1] = 1、dp[2] = 2。记忆化搜索引入数组 mem 记录已算出的非基本状态值,基本情况先直接返回,非基本状态先查记录,仅在未记录时才继续向下展开。
画面中的首次计算主链为 dp[9] → dp[8] → dp[7] → … → dp[3],中间 dp[6] 至 dp[4] 用省略号代替;dp[3] 再分为基本情况 dp[2] 和 dp[1]。右侧明确画出带剪刀的缓存复用 dp[7]、dp[6]、dp[5],其余复用位置用省略号概括。按代码补全省略段,还会在 dp[6] 中复用 dp[4]、在 dp[5] 中复用 dp[3];dp[4] 的右子问题 dp[2] 是直接返回的基本情况,不属于缓存命中。
例如求 dp[9] 时先完成左子问题 dp[8],此过程中已经计算并保存 dp[7];随后求右子问题(带剪刀的 dp[7]),直接读缓存而不再重复展开,它仍参与 dp[9] 的加法。
下方两表分别列出图中三处明确标出的复用关系,以及代码对基本情况、首次计算、缓存命中的不同处理。
| 当前父状态 | 先完成的左子问题 | 随后读取记录的右子问题 |
|---|---|---|
| dp[9] | dp[8] | dp[7] |
| dp[8] | dp[7] | dp[6] |
| dp[7] | dp[6](图中以省略号代替) | dp[5] |
| 遇到的状态 | 处理 |
|---|---|
| dp[1]、dp[2] | 直接返回 1、2 |
| 非基本状态,尚无记录 | 递归计算、相加、写入 mem 后返回 |
| 非基本状态,已有记录 | 直接返回 mem 中的值,贡献仍参与加法 |
每个非基本状态只展开计算一次,重复请求直接返回缓存值,时间复杂度因此降为 O(n)。
14.1.3 方法三:动态规划¶
记忆化搜索是一种“从顶至底”的方法:我们从原问题(根节点)开始,递归地将较大子问题分解为较小子问题,直至解已知的最小子问题(叶节点)。之后,通过回溯逐层收集子问题的解,构建出原问题的解。
与之相反,动态规划是一种“从底至顶”的方法:从最小子问题的解开始,迭代地构建更大子问题的解,直至得到原问题的解。
由于动态规划不包含回溯过程,因此只需使用循环迭代实现,无须使用递归。在以下代码中,我们初始化一个数组 dp 来存储子问题的解,它起到了与记忆化搜索中数组 mem 相同的记录作用:
/* 爬楼梯:动态规划 */
func climbingStairsDP(n: Int) -> Int {
if n == 1 || n == 2 {
return n
}
// 初始化 dp 表,用于存储子问题的解
var dp = Array(repeating: 0, count: n + 1)
// 初始状态:预设最小子问题的解
dp[1] = 1
dp[2] = 2
// 状态转移:从较小子问题逐步求解较大子问题
for i in 3 ... n {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}
/* 爬楼梯:动态规划 */
function climbingStairsDP(n) {
if (n === 1 || n === 2) return n;
// 初始化 dp 表,用于存储子问题的解
const dp = new Array(n + 1).fill(-1);
// 初始状态:预设最小子问题的解
dp[1] = 1;
dp[2] = 2;
// 状态转移:从较小子问题逐步求解较大子问题
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
/* 爬楼梯:动态规划 */
function climbingStairsDP(n: number): number {
if (n === 1 || n === 2) return n;
// 初始化 dp 表,用于存储子问题的解
const dp = new Array(n + 1).fill(-1);
// 初始状态:预设最小子问题的解
dp[1] = 1;
dp[2] = 2;
// 状态转移:从较小子问题逐步求解较大子问题
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
/* 爬楼梯:动态规划 */
int climbingStairsDP(int n) {
if (n == 1 || n == 2) return n;
// 初始化 dp 表,用于存储子问题的解
List<int> dp = List.filled(n + 1, 0);
// 初始状态:预设最小子问题的解
dp[1] = 1;
dp[2] = 2;
// 状态转移:从较小子问题逐步求解较大子问题
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
/* 爬楼梯:动态规划 */
fn climbing_stairs_dp(n: usize) -> i32 {
// 已知 dp[1] 和 dp[2] ,返回之
if n == 1 || n == 2 {
return n as i32;
}
// 初始化 dp 表,用于存储子问题的解
let mut dp = vec![-1; n + 1];
// 初始状态:预设最小子问题的解
dp[1] = 1;
dp[2] = 2;
// 状态转移:从较小子问题逐步求解较大子问题
for i in 3..=n {
dp[i] = dp[i - 1] + dp[i - 2];
}
dp[n]
}
/* 爬楼梯:动态规划 */
int climbingStairsDP(int n) {
if (n == 1 || n == 2)
return n;
// 初始化 dp 表,用于存储子问题的解
int *dp = (int *)malloc((n + 1) * sizeof(int));
// 初始状态:预设最小子问题的解
dp[1] = 1;
dp[2] = 2;
// 状态转移:从较小子问题逐步求解较大子问题
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int result = dp[n];
free(dp);
return result;
}
可视化运行
图 14-5 模拟了以上代码的执行过程。
图 14-5 爬楼梯的动态规划过程
图解 14-5:从初始状态迭代计算爬楼梯方案数
从初始状态 dp[1] = 1、dp[2] = 2 出发,每次将相邻前两项相加,自左向右迭代推算至 dp[9]。
爬楼梯每步可上 1 阶或 2 阶,dp[i] 表示爬到第 i 阶的方案数。本图展示自底向上的动态规划填表过程,无需借助递归调用栈。
先设置 dp[1] = 1、dp[2] = 2,再按 dp[3] 到 dp[9] 顺序依次计算 dp[i] = dp[i − 1] + dp[i − 2]:因为每项只依赖前两项,而计算到该项时它们都已先算出。
图中九个方块横向排列,只写状态名 dp[1] 至 dp[9];下方另标初值 dp[1] = 1、dp[2] = 2 和状态转移公式。数值 3、5、8、13、21、34 以及 dp[9] 的 55 均由这些初值和公式推算,并非方块中的标值。下表对应列出初值、依赖与推算结果。
| 状态 | 来源 | 值及依据 |
|---|---|---|
| dp[1] | 初始状态 | 1(图中给定初值) |
| dp[2] | 初始状态 | 2(图中给定初值) |
| dp[3] | dp[2] + dp[1] | 3(由公式推算) |
| dp[4] | dp[3] + dp[2] | 5(由公式推算) |
| dp[5] | dp[4] + dp[3] | 8(由公式推算) |
| dp[6] | dp[5] + dp[4] | 13(由公式推算) |
| dp[7] | dp[6] + dp[5] | 21(由公式推算) |
| dp[8] | dp[7] + dp[6] | 34(由公式推算) |
| dp[9] | dp[8] + dp[7] | 55(由公式推算) |
自底向上迭代时每个状态只计算一次,到达目标状态即终止;按图中初始值与转移公式推算,目标 dp[9] 对应的方案数为 55。
与回溯算法一样,动态规划也使用“状态”概念来表示问题求解的特定阶段,每个状态都对应一个子问题以及相应的局部最优解。例如,爬楼梯问题的状态定义为当前所在楼梯阶数 \(i\) 。
根据以上内容,我们可以总结出动态规划的常用术语。
- 将数组
dp称为 dp 表,\(dp[i]\) 表示状态 \(i\) 对应子问题的解。 - 将最小子问题对应的状态(第 \(1\) 阶和第 \(2\) 阶楼梯)称为初始状态。
- 将递推公式 \(dp[i] = dp[i-1] + dp[i-2]\) 称为状态转移方程。
14.1.4 空间优化¶
细心的读者可能发现了,由于 \(dp[i]\) 只与 \(dp[i-1]\) 和 \(dp[i-2]\) 有关,因此我们无须使用一个数组 dp 来存储所有子问题的解,而只需两个变量滚动前进即可。代码如下所示:
可视化运行
观察以上代码,由于省去了数组 dp 占用的空间,因此空间复杂度从 \(O(n)\) 降至 \(O(1)\) 。
在动态规划问题中,当前状态往往仅与前面有限个状态有关,这时我们可以只保留必要的状态,通过“降维”来节省内存空间。这种空间优化技巧被称为“滚动变量”或“滚动数组”。