今天是我们讲解「动态规划专题」中的 路径问题 的第九天。
我在文章结尾处列举了我所整理的关于「路径问题」的相关题目。
「路径问题」我会按照编排好的顺序进行讲解(一天一道)。
你也先可以尝试做做,也欢迎你向我留言补充,你觉得与路径相关的 DP 类型题目 ~
这是 LeetCode 上的「576. 出界的路径数」,难度为 Medium。
给定一个 的网格和一个球。
球的起始坐标为 ,你可以将球移到相邻的单元格内,或者往上、下、左、右四个方向上移动使球穿过网格边界。
但是,你最多可以移动 次。
找出可以将球移出边界的路径数量。答案可能非常大,返回结果 mod + 7 的值。
示例 1:
输入: m = 2, n = 2, N = 2, i = 0, j = 0
输出: 6
解释:
示例 2:
输入: m = 1, n = 3, N = 3, i = 0, j = 1
输出: 12
解释:
说明:
还记得我在 上一节 和你说的两种「动态规划」求解方法吗?
我们来回顾一下:
1. 根据经验猜一个「状态定义」,然后根据「状态定义」去推导一个「状态转移方程」。
2. 先写一个「记忆化搜索」解法,再将「记忆化搜索」改写成「动态规划」。
为了方便区分这两种方法,我们称第一种解法为「经验解法」,第二种为「技巧解法」吧。
其中「技巧解法」是我上一节教你的,今天我们也将使用这种解法解决本题。
来强化我们对「技巧解法」的熟练度。
由于我们的「技巧解法」是将「记忆化搜索」翻译成「动态规划」。
因此我们需要先有一个「记忆化搜索」解法。
但我在 上一节 的「总结」部分也跟你强调过,所谓的有一个「记忆化搜索」,我们只需要考虑 DFS 函数会如何设计即可,而不需要真正去实现一个「记忆化搜索」。
那么如果是让你设计一个 DFS 函数来解决本题,你会如何设计?
如果是我的话,我大概会这样设计:
int dfs(int m, int n, int x, int y, int k) {}
其中 和 是对应了题目的源输入,用来表示矩形是几行几列的,整个 DFS 过程都不会发生变化,因此我们无须理会。
代表当前所在的位置, 代表最多的移动次数,返回值代表路径数量。
重点放在 DFS 函数签名中的「可变参数」与「返回值」。这和我们【动态规划】中的「状态定义」强关联。
同时为了方便,我们可以将 根据以下规则映射为一个独立的编号 :
index = x * n + y;
(x, y) = (index / n, index % n);
根据我们的「技巧解法」,我们可以设计一个二维数组 作为我们的 dp 数组:
dp 数组中存储的就是我们 DFS 的返回值:路径数量。
根据 dp 数组中的维度设计和存储目标值,我们可以得知「状态定义」为:
代表从位置 出发,可用步数不超过 时的路径数量。
至此,我们没有实现「记忆化搜索」,只是设计了 DFS 函数的签名,就已经得出我们的「状态定义」了,接下来需要考虑「转移方程」。
当有了「状态定义」之后,我们需要从「最后一步」来推导出「转移方程」:
由于题目允许往四个方向进行移动。
因此我们的最后一步也要统计四个相邻的方向。
举个?,假设我们当前位置为,而 四个方向的相邻格子均不超出矩形。即有:
出发的路径数量 = 上方 的路径数量 + 下方 的路径数量 + 左方 的路径数量 + 右方 (x,y+1)$ 的路径数量
由此可得我们的状态转移方程:
PS. 转移方程中 dp 数组的第一维存储的是 对应的 。
从转移方程中我们发现,更新 依赖于 ,因此我们转移过程中需要将最大移动步数进行从小到大枚举。
至此,我们已经完成求解「路径规划」问题的两大步骤:「状态定义」&「转移方程」。
但这还不是所有,我们还需要一些「有效值」来滚动下去。
其实就是需要一些「有效值」作为初始化状态。
观察我们的「转移方程」可以发现,整个转移过程是一个累加过程,如果没有一些有效的状态(非零值)进行初始化的话,整个递推过程并没有意义。
那么哪些值可以作为成为初始化状态呢?
显然,当我们已经位于矩阵边缘的时候,我们可以一步跨出矩阵,这算作一条路径。
同时,由于我们能够往四个方向进行移动,因此不同的边缘格子会有不同数量的路径。
换句话说,我们需要先对边缘格子进行初始化操作,预处理每个边缘格子直接走出矩阵的路径数量。
目的是为了我们整个 DP 过程可以有效的递推下去。
代码:
class Solution {
int mod = (int)1e9+7;
int m, n, N;
public int findPaths(int _m, int _n, int _N, int _i, int _j) {
m = _m; n = _n; N = _N;
// f[i][j] 代表从 idx 为 i 的位置出发,移动步数不超过 j 的路径数量
int[][] f = new int[m * n][N + 1];
// 初始化边缘格子的路径数量
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0) add(i, j, f);
if (i == m - 1) add(i, j, f);
if (j == 0) add(i, j, f);
if (j == n - 1) add(i, j, f);
}
}
// 定义可移动的四个方向
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
// 从小到大枚举「可移动步数」
for (int step = 1; step <= N; step++) {
// 枚举所有的「位置」
for (int k = 0; k < m * n; k++) {
int x = parseIdx(k)[0], y = parseIdx(k)[1];
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
// 如果位置有「相邻格子」,则「相邻格子」参与状态转移
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
f[k][step] += f[getIndex(nx, ny)][step - 1];
f[k][step] %= mod;
}
}
}
}
// 最终结果为从起始点触发,最大移动步数不超 N 的路径数量
return f[getIndex(_i, _j)][N];
}
// 为每个「边缘」格子,添加一条路径
void add(int x, int y, int[][] f) {
int idx = getIndex(x, y);
for (int step = 1; step <= N; step++) {
f[idx][step]++;
}
}
// 将 (x, y) 转换为 index
int getIndex(int x, int y) {
return x * n + y;
}
// 将 index 解析回 (x, y)
int[] parseIdx(int idx) {
return new int[]{idx / n, idx % n};
}
}
如果你有理解透彻 路径问题第八讲 中的内容的话,今天这道题应该是一道练习题。
帮助你加强对【动态规划】中的「技巧解法」的掌握。
如果你已经认真学过 路径问题第八讲,但是还是觉得本题难以入手,也没有关系。
我教给你都是【动态规划】中的通解,真正理解掌握往往需要多重复。
重复不仅仅是指你要多刷题,而是要始终带着我与你分享的「分析思路」去解决动态规划问题。
最后,我十分建议你将 路径问题 系列的每一讲多看几遍,这些内容不仅仅是「路径问题」相关题解,更是【动态规划】问题的通用解决方案。
这些都是三叶多年 OI 经历所总结的精华,希望你会认真的看哦 ~
62.不同路径(中等):路径问题第一讲
63.不同路径 II(中等):路径问题第二讲
64.最小路径和(中等):路径问题第三讲
120.三角形最小路径和(中等):路径问题第四讲
931.下降路径最小和(中等):路径问题第五讲
1289.下降路径最小和 II(困难):路径问题第六讲
1575.统计所有可行路径(困难):路径问题第七讲(记忆化搜索)
1575.统计所有可行路径(困难):路径问题第八讲(动态规划)
576.出界的路径数(中等):本篇
1301.最大得分的路径数目(困难)
欢迎补充 ~
这是我们「刷穿 LeetCode」系列文章的第 No.576
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。