动态规划应用 | LianoのBlog

AI summary

type

status

date

slug

summary

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

其实这道题难度不算大，但你可能会遇到一些难度比较大的变体，所以统一讲一讲这种问题的通用思路。

一般来说，让你在二维矩阵中求最优化问题（最大值或者最小值），肯定需要递归 + 备忘录，也就是动态规划技巧。

定义从 (0,0) 走到 (i,j) 的最小路径和为 dp(grid,i,j) 。

然后就可以直接写代码了：

能不能用自底向上的迭代解法来做这道题呢？完全可以的。dp 数组的定义和上面一样，base case 略有不同，代码如下：

当然也可以空间压缩，只取决于 dp[i-1][j] 和 dp[i][j-1]，前者等于当前还未更新的 dp[j]，后者等于当前已经更新过的 dp[j-1]（正向遍历）。

地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只向右或向下移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

简单说，就是问你至少需要多少初始生命值，能够让骑士从最左上角移动到最右下角，且任何时候生命值都要大于 0。

想要最小化骑士的初始生命值，是不是意味着要最大化骑士行进路线上的血瓶？是不是相当于求「最大路径和」？是不是可以直接套用计算「最小路径和」的思路？

但是稍加思考，发现这个推论并不成立，吃到最多的血瓶，并不一定就能获得最小的初始生命值。

比如如下这种情况，如果想要吃到最多的血瓶获得「最大路径和」，应该按照下图箭头所示的路径，初始生命值需要 11。

但也很容易看到正确的答案应该是走中间，初始生命值只需要 1。

按照常理，这个 dp 函数的定义应该是：

从左上角（grid[0][0]）走到 grid[i][j] 至少需要 dp(grid, i, j) 的生命值。

但是按照 dp 函数的定义，你只知道「能够从左上角到达 B 的最小生命值」，但并不知道「到达 B 时的生命值」，这样无法进行状态转移。

所以我们应该倒着定义：

从 grid[i][j] 走到右下角至少需要 dp(grid, i, j) 的生命值。这样就知道了在每个点至少需要留存多少生命值。

定义好 dp 函数/数组就很简单了，直接看自底向上的代码吧：

自由之路

给你输入一个字符串 ring 代表圆盘上的字符（指针位置在 12 点钟方向，初始指向 ring[0]），再输入一个字符串 key 代表你需要拨动圆盘输入的字符串，你的算法需要返回输入这个 key 至少进行多少次操作（拨动一格圆盘和按下圆盘中间的按钮都算是一次操作）。

这个问题如何使用动态规划的技巧解决呢？或者说，这道题的「状态」和「选择」是什么呢？

「状态」就是「当前需要输入的字符」和「当前圆盘指针的位置」。

再具体点，「状态」就是 i 和 j 两个变量。我们可以用 i 表示当前圆盘上指针指向的字符（也就是 ring[i]）；用 j 表示需要输入的字符（也就是 key[j]）。

dp 函数的定义如下：

当圆盘指针指向 ring[i] 时，输入字符串 key[j..] 至少需要 dp(ring, i, key, j) 次操作。

根据这个定义，题目其实就是想计算 dp(ring, 0, key, 0) 的值。base case 为 dp[..][len(key)] = 0。

接下来，思考一下如何根据状态做选择，如何进行状态转移？

「选择」就是「如何拨动指针得到待输入的字符」。

首先要知道 key[j] 在圆盘的哪些位置上，然后每个位置有两种情况，顺时针或者逆时针。我们需要选择操作次数最少的那个拨法。当前操作次数最少不一定是离得最近的那个，因为还与之后的 key 有关。

代码如下：

K 站中转内最便宜的航班

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。如果不存在这样的路线，则输出 -1。

很明显，这题就是个加权有向图中求最短路径的问题。

说白了，就是给你一幅加权有向图，让你求 src 到 dst 权重最小的一条路径，同时要满足，这条路径最多不能超过 K + 1 条边（经过 K 个节点相当于经过 K + 1 条边）。

我们来分析下求最短路径相关的算法。

「BFS 算法思路」

求最短路径，肯定可以用 BFS 算法来解决。不过呢，对于加权图的最短路径来说，得用优先级队列，也就是 Dijkstra 算法。

但是这题有中转次数 k 的限制，所以需要额外的剪枝。代码如下：

注意，不能把 cost 大但是 stops 小的给剪掉了，因为最短路径不一定满足最多中转 k 次。

「动态规划思路」

求最值的问题，很多都可能使用动态规划来求解。

加权最短路径问题，再加个 K 的限制也无妨，不也是个求最值的问题嘛，动态规划统统拿下。

dp 函数定义如下：

从起点 src 出发，k 步（一步就是一条边）到达节点 s 的最小路径权重为 dp(s, k)。

其实就是 Bellman-Ford 算法。

阈值距离内邻居最少的城市

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
返回在路径距离限制为 distanceThreshold 以内可到达城市最少的城市。如果有多个这样的城市，则返回编号最大的城市。

Floyd 算法用于计算多源最短路径。

只需要记住最外层 for 循环穷举 k，里面两层穷举 i, j，dp[i][j] 的值是 dp[i][k] + dp[k][j] 的最小值，就能写出 Floyd 算法了。

上面的状态转移的正确性不好看出，其实是因为这是状态压缩后的结果。原 dp 数组定义为：仅经过前 k 个节点中的若干个节点（可以选择性经过，不必都经过），节点 i 到节点 j 的最短路径权重为 dp[k][i][j]。

压缩过程有点复杂，这里略了。

正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

我们先脑补一下，s 和 p 相互匹配的过程大致是，两个指针 i, j 分别在 s 和 p 上移动，如果最后两个指针都能移动到字符串的末尾，那么久匹配成功，反之则匹配失败。

「状态」就是 i，j，定义 dp 数组如下：

dp[i][j] = True 表示 s[:i] 可以匹配 p[:j]。

base case 为 dp[0][0] = True，接下来分类讨论做「选择」来获得状态转移方程。

p[j-1] 不等于 ‘*’ 时，取决于 p[j-1] 是否等于 s[i-1] 以及 dp[i-1][j-1]；

p[j-1] 等于 ‘*’ 时，p[j-2] 可以匹配 0 次或多次；

匹配 0 次时，取决于 dp[i][j-2]；

匹配多次时，取决于 p[j-2] 是否等于 s[i-1] 以及 dp[i-1][j]；

代码如下：

鸡蛋掉落

你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于 F 的楼层都会碎，低于 F 的楼层都不会碎，如果鸡蛋没有碎，可以捡回来继续扔）。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

经典面试题，参考 https://www.bilibili.com/video/BV1KE41137PK/

代码如下：

细心的读者可能会问，在第 i 层楼扔鸡蛋如果没碎，楼层的搜索区间缩小至上面的楼层，是不是应该包含第 i 层楼呀？不必，因为已经包含了。开头说了 F 是可以等于 0 的，向上递归后，第 i 层楼其实就相当于第 0 层，可以被取到，所以说并没有错误。

另外，要注意 0 <= F <= N ，所以区间是左闭右闭的，所以 base case 需要有 j 为 0 的情况。

这种解法时间复杂度为，会超时。

「二分搜索优化」

修改代码中的 for 循环为二分搜索，可以将时间复杂度降为。

下面解释一下为什么能二分，状态转移方程如下：

首先我们根据 dp(K, N) 数组的定义（有 K 个鸡蛋面对 N 层楼，最少需要扔几次），很容易知道 K 固定时，这个函数随着 N 的增加一定是单调递增的，无论你策略多聪明，楼层增加测试次数一定要增加。

那么注意 dp(K - 1, i - 1) 和 dp(K, N - i) 这两个函数，其中 i 是从 1 到 N 单增的，如果我们固定 K 和 N，把这两个函数看做关于 i 的函数，前者随着 i 的增加应该也是单调递增的，而后者随着 i 的增加应该是单调递减的：

这时候求二者的较大值，再求这些最大值之中的最小值，其实就是求这两条直线交点，也就是红色折线的最低点嘛。

熟悉二分搜索的同学肯定敏感地想到了，这不就是相当于求 Valley（山谷）值嘛，可以用二分查找来快速寻找这个点的。

当然，python 的这个算法还是超时了。。。

「重新定义 dp 数组」

找动态规划的状态转移本就是见仁见智，比较玄学的事情，不同的状态定义可以衍生出不同的解法，其解法和复杂程度都可能有巨大差异，这里就是一个很好的例子。

定义 dp[k][m] = n 表示有 k 个鸡蛋，最多允许扔 m 次，可以确定最高 n 层。

原始解法还得线性或者二分扫描所有楼层，要求最大值、最小值。但是现在这种 dp 定义根本不需要这些了，基于下面两个事实：

无论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。

无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。

所以状态转移方程为：dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1

代码如下：

如果你还觉得这段代码有点难以理解，其实它就等同于这样写：

时间复杂度为，终于可以过了😋

戳气球

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。

这个动态规划问题和我们之前的动态规划系列文章相比有什么特别之处？为什么它比较难呢？

原因在于，这个问题中我们每戳破一个气球 nums[i]，得到的分数和该气球相邻的气球 nums[i-1] 和 nums[i+1] 是有相关性的。

动态规划算法的重要条件：子问题必须独立。所以对于这个戳气球问题，如果想用动态规划，必须巧妙地定义 dp 数组的含义，避免子问题产生相关性，才能推出合理的状态转移方程。

如何定义 dp 数组呢，这里需要对问题进行一个简单地转化。题目说可以认为 nums[-1] = nums[n] = 1，那么我们先直接把这两个边界加进去，形成一个新的数组 points ，两端是虚拟节点。

现在可以定义 dp 数组的含义：

dp[i][j] = x 表示，戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球，可以获得的最高分数为 x。

那么根据这个定义，题目要求的结果就是 dp[0][n+1] 的值，而 base case 就是 dp[i][j] = 0，其中 0 <= i <= n+1, j <= i+1，因为这种情况下，开区间 (i, j) 中间根本没有气球可以戳。

假设 k 是最后一个戳破的气球，那么状态转移方程为：

dp[i][j] = dp[i][k] + dp[k][j] + points[i]*points[k]*points[j]

按照什么顺序穷举状态呢？

关于「状态」的穷举，最重要的一点就是：状态转移所依赖的状态必须被提前计算出来。

拿这道题举例，dp[i][j] 所依赖的状态是 dp[i][k] 和 dp[k][j]，那么我们必须保证：在计算 dp[i][j] 时，dp[i][k] 和 dp[k][j] 已经被计算出来了（其中 i < k < j）。

画图如下：

那么，为了达到这个要求，可以有两种遍历方法，要么斜着遍历，要么从下到上从左到右遍历。

斜着遍历有一点难写，所以一般我们就从下往上遍历，下面看完整代码：

这里 j 从 i+2 开始，因为 j=i+1 是 base case。i 从 n-3 开始也是因为最少有三个气球。

石子游戏

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有正整数颗石子，数目为 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
Alice 和 Bob 轮流进行，Alice 先开始 。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家获胜。
假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

dp[i][j] 表示剩下第 i 到 j 堆时先手与后手的差值。

代码如下：

这里的 dp 数组定义也比较巧妙，如果定义为最大值，那么就需要用 sum(i,j) 来减，比较麻烦。

另外，对于这个状态转移方程，i 需要反向遍历，i 和 j 的初始值与上题同理。

其实呢，这道题是先手必胜的，没想到吧：

alice 可以控制选到所有在奇数/偶数组中的元素，只要事先计算出哪组大就必胜。所以如果 bob 真的足够聪明，那么他会直接认输。

预测赢家

上题的一般形式，堆数不一定是偶数。

直接用上面的函数即可。

打家劫舍问题

今天来讲「打家劫舍」系列问题（英文版叫 House Robber），这个系列是比较有代表性和技巧性的动态规划题目。

打家劫舍系列总共有三道，难度设计比较合理，层层递进。第一道是比较标准的动态规划问题，而第二道融入了环形数组的条件，第三道更绝，把动态规划的自底向上和自顶向下解法和二叉树结合起来，我认为很有启发性。

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

dp[i] 表示前 1～i 个房间抢得到的最高金额。（因为状态转移方程有 i-2，所以 i 从 2 开始比较方便）

「选择」是抢或者不抢第 i 个房间。

打家劫舍 Ⅱ

和上一道题描述基本一样，强盗依然不能抢劫相邻的房子，输入依然是一个数组，但是告诉你这些房子不是一排，而是围成了一个圈。

这个约束条件看起来应该不难解决，我们前文 单调栈问题汇总 说过一种解决环形数组的方案，那么在这个问题上怎么处理呢？

首先，首尾房间不能同时被抢，那么只可能有三种不同情况：要么都不被抢；要么最后一间不抢；要么第一间不抢。

那就简单了啊，这三种情况，哪种的结果最大，就是最终答案呗！不过，其实我们不需要比较三种情况，只要比较情况二和情况三就行了，因为这两种情况对于房子的选择余地比情况一大呀，房子里的钱数都是非负数，所以选择余地大，最优决策结果肯定不会小。

打家劫舍 Ⅲ

此强盗发现现在面对的房子不是一排，不是一圈，而是一棵二叉树！房子在二叉树的节点上，相连的两个房子不能同时被抢劫。

树的结构天然的适合递归，而且由于没有指向父节点的指针，所以自顶向下的递归解法更合适。

定义 dp(root) 表示以 root 为根的子树的最大值。状态转移和前面一样，选择抢或者不抢 root。

分析下时间复杂度，虽然看这个递归结构似乎是一棵四叉树，但实际上由于备忘录的优化，递归函数做的事情就是还是遍历每个节点，不会多次进入同一个节点，所以时间复杂度是还是

还有更优雅的解法：

这种解法相当于后续遍历，每个 node 只会计算一次，所以不需要备忘录。上一种解法每个节点可以从父节点访问到，也可能从爷爷节点访问到，所以需要备忘录。

股票买卖问题

很多读者抱怨力扣上的股票系列问题的解法太多，如果面试真的遇到这类问题，基本不会想到那些巧妙的办法，怎么办？所以本文不讲那些过于巧妙的思路，而是稳扎稳打，只用一种通用方法解决所有问题，以不变应万变。

这篇文章参考 英文版高赞题解 的思路，用状态机的技巧来解决，可以全部提交通过。不要觉得这个名词高大上，文学词汇而已，实际上就是 DP table，看一眼就明白了。

我们只需要抽出来力扣第 188 题「买卖股票的最佳时机 IV」进行研究，因为这道题是最泛化的形式，其他的问题都是这个形式的简化。

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。