登录
Hello 算法：“走一步看一步”的智慧
每个系列一本前端好书，帮你轻松学重点。
本系列来自上海交通大学硕士，华为高级算法工程师 靳宇栋 的 《Hello，算法》
“走一步看一步”，是我们面对不断变化的世界所采取的应对策略。
多数时候，我们无法对未来做出准确预测，只能根据上一件事的结果对下一件事做决策。介绍“分治”的时候，我们已经接触过这种策略。本篇主角依然如此，但又有所不同。
先看个例子。
爬楼梯
给一个 n 阶楼梯，每步可以上 1 阶或者 2 阶，问有多少种方案可以爬到楼顶？
假设 n 是3，那么方案共 3 种。如下图所示。
这种方案采用的是“穷举”，每轮选择上 1 阶或 2 阶，每当到达顶部时就将方案数量加 1，当越过顶部时就将其剪枝。
这是一种将问题看做一系列决策步骤的方案，我们还可以尝试从问题分解的角度分析。
暴力搜索
假设，爬到第 i 阶有 dp(i)种方案，那么dp(i)就是原问题，子问题包括：
由于每轮只能上 1 阶或 2 阶，因此，我们只能从第 i-1阶或第 i-2 阶迈向第 i 阶。
可得出一个重要推论：爬到第 i -2 阶的方案数加上爬到第 i-1 阶的方案数就等于爬到第 i 阶的方案数。
这意味着在爬楼梯问题中，各个子问题之间存在递推关系，原问题的解可以由子问题的解构建得来。如下图所示：
代码实现：
/* 搜索 */
function dfs(i) {
// 已知 dp[1] 和 dp[2] ，返回之
if (i === 1 || i === 2) return i;
// dp[i] = dp[i-1] + dp[i-2]
const count = dfs(i - 1) + dfs(i - 2);
return count;
}
/* 爬楼梯：搜索 */
function climbingStairsDFS(n) {
return dfs(n);
}
看到一个熟悉的身影—“递归”，暴力搜索会形成一个递归树，对于问题 dp[n]，其递归树的深度为 n，时间复杂度为O(2n)。
情况不太妙，因为指数阶具备爆炸式增长的特点，如果输入一个比较大的 n ，会陷入漫长的等待。
时间复杂度为何如此之高？我们观察一下递归树。
聪明的你一眼就看出，这棵树出现了多个相同的“子问题”，大部分计算资源都浪费在这些重叠的子问题上。
那么，优化的措施就有了。
记忆化搜索
为提升效率，需要做的改进是：重叠子问题只计算一次。
为此，我们声明一个数组 mem 来记录子问题的解，并在搜索过程中将重叠子问题剪枝。
- 首次计算 dp[i] 时，将其记录至
mem[i]，以便之后使用。 - 再次需要计算 dp[i] 时，直接从
mem[i]中获取结果，避免重复计算。
代码实现：
/* 记忆化搜索 */
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);
}
简化后，所有重复子问题都只计算1次，时间复杂度为O(n)，这是一个巨大的飞跃。
那么，记忆化搜索是否还存在短板，有继续优化的可能吗？
细心的朋友发现了，记忆化搜索“基于递归”的，这意味着：
1、每个子问题都需要一次函数调用，函数调用需要时间成本；
2、当数据量很大时，可能产生调用栈溢出；
怎么办？
动态规划
记忆化搜索流程是“始于原问题，分解成小问题”，通过回溯收集子问题的解，构建原问题的解。可称为 “从顶至底”。
与之相反，动态规划是一种 “从底至顶” 的方法，“从最小子问题的解开始，迭代地构建更大子问题的解”，直至得到原问题的解。
由于动态规划不包含“回溯”过程，就无须使用递归，只需循环迭代。
代码实现：
/* 爬楼梯：动态规划 */
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];
}
空间优化
如果继续“吹毛求疵”，会发现，我们要求解的是dp[i]，而dp[i] 只与 dp[i-1] 和 dp[i-2] 有关，上面代码返回的却是dp[n]？
完全没必要，所以它还有改进空间，便是去除数组，采用两个变量滚动前进。
/* 爬楼梯：空间优化后的动态规划 */
function climbingStairsDPComp(n) {
if (n === 1 || n === 2) return n;
let a = 1,
b = 2;
for (let i = 3; i <= n; i++) {
const tmp = b;
b = a + b;
a = tmp;
}
return b;
}
由于省去了数组占用的空间，空间复杂度从 O(n) 降至 O(1) ，再次大幅优化。
我们可以触类旁通地认为，在动态规划问题中，当前状态往往仅与前面有限个状态有关，可以只保留必要的状态，通过“降维”来节省内存空间。
这种空间优化技巧被称为 “滚动变量” 或 “滚动数组” 。
子问题玄机
本篇文章，我们再次提到“子问题”，“子问题”分解是一种通用的算法思路，之前你肯定就见过，那么，它们之间的区别是什么？
- 分治算法：强调子问题相互独立。
- 动态规划：子问题是相互依赖的，在分解过程中会出现许多重叠子问题。
- 回溯算法：原问题的解由一系列决策步骤构成，每个决策步骤之前的子序列可看作一个子问题。
识别动态规划
如何判断一个问题是不是动态规划？
总的来说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型。
在此基础上，还有一些判断的“加分项”。
- 问题包含最大（小）或最多（少）等最优化描述。
- 问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。
小结
本篇文章系统讲解了动态规划的特点和核心实现，除了上面介绍的“爬楼梯”，还有什么常见适用场景吗？
0-1 背包：求解“在限定背包容量下能放入物品的最大价值”，满足决策树模型，含有“最大”关键词。
编辑距离：求解两个字符串之间互相转换的最少修改次数，通常用于在信息检索和自然语言处理中度量两个序列的相似度。当下最火的大语言模型中，就广泛存在此类应用。
动态规划还有很多应用场景，且不易掌握和解决，需要大家正确理解和多练习才行，一起加油！~
更多好文章第一时间推送，可关注公众号：前端说书匠
