【刷穿 LeetCode】576. 出界的路径数 :「记忆化搜索」&「动态规划」-阿里云开发者社区

网络异常，图片无法展示

题目描述

这是 LeetCode 上的 576. 出界的路径数 ，难度为中等。

Tag : 「路径 DP」、「动态规划」、「记忆化搜索」

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。

你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。

你最多可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。

因为答案可能非常大，返回对 10^9 + 7109+7 取余后的结果。

示例 1：

网络异常，图片无法展示

输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6
复制代码

示例 2：

网络异常，图片无法展示

输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
输出：12
复制代码

提示：

1 <= m, n <= 50
0 <= maxMove <= 50
0 <= startRow < m
0 <= startColumn < n

基本分析

通常来说，朴素的路径 DP 问题之所以能够使用常规 DP 方式进行求解，是因为只能往某一个方向（一维棋盘的路径问题）或者只能往某两个方向（二维棋盘的路径问题）移动。

这样的移动规则意味着，我们不会重复进入同一个格子。

从图论的意义出发：将每个格子视为点的话，如果能够根据移动规则从 a 位置一步到达 b 位置，则说明存在一条由 a 指向 b 的有向边。

也就是说，在朴素的路径 DP 问题中，“单向”的移动规则注定了我们的图不存在环，是一个存在拓扑序的有向无环图，因此我们能够使用常规 DP 手段来求解。

回到本题，移动规则是四联通，并不是“单向”的，在某条出界的路径中，我们是有可能重复进入某个格子，即存在环。

因此我们需要换一种 DP 思路进行求解。

记忆化搜索

通常在直接 DP 不好入手的情况下，我们可以先尝试写一个「记忆化搜索」的版本。

那么如果是让你设计一个 DFS 函数来解决本题，你会如何设计？

我大概会这样设计：

int dfs(int x, int y, int k) {}
复制代码

重点放在几个「可变参数」与「返回值」上：(x,y)(x,y) 代表当前所在的位置，kk 代表最多使用多少步，返回值代表路径数量。

根据 DP-动态规划第八讲的学习中，我们可以确定递归出口为：

当前到达了棋盘外的位置，说明找到了一条出界路径，返回 11；
在条件 11 不满足的前提下，当剩余步数为 00（不能再走下一步），说明没有找到一条合法的出界路径，返回 00。

主逻辑则是根据四联通规则进行移动即可，最终答案为 dfs(startRow, startColumn, maxMove)。

代码：

class Solution {
    int MOD = (int)1e9+7;
    int m, n, max;
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int[][][] cache;
    public int findPaths(int _m, int _n, int _max, int r, int c) {
        m = _m; n = _n; max = _max;
        cache = new int[m][n][max + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= max; k++) {
                    cache[i][j][k] = -1;
                }
            }
        }
        return dfs(r, c, max);
    }
    int dfs(int x, int y, int k) {
        if (x < 0 || x >= m || y < 0 || y >= n) return 1;
        if (k == 0) return 0;
        if (cache[x][y][k] != -1) return cache[x][y][k];
        int ans = 0;
        for (int[] d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            ans += dfs(nx, ny, k - 1);
            ans %= MOD;
        }
        cache[x][y][k] = ans;
        return ans;
    }
}
复制代码

动态规划

根据我们的「记忆化搜索」，我们可以设计一个二维数组 f[][]f[][] 作为我们的 dp 数组：

第一维代表 DFS 可变参数中的 (x,y)(x,y) 所对应 indexindex。取值范围为 [0, m*n)[0,m∗n)
第二维代表 DFS 可变参数中的 kk。取值范围为 [0,max][0,max]

dp 数组中存储的就是我们 DFS 的返回值：路径数量。

根据 dp 数组中的维度设计和存储目标值，我们可以得知「状态定义」为：

f[i][j]f[i][j] 代表从位置 ii 出发，可用步数不超过 jj 时的路径数量。

至此，我们只是根据「记忆化搜索」中的 DFS 函数的签名，就已经得出我们的「状态定义」了，接下来需要考虑「转移方程」。

当有了「状态定义」之后，我们需要从「最后一步」来推导出「转移方程」：

由于题目允许往四个方向进行移动，因此我们的最后一步也要统计四个相邻的方向。

由此可得我们的状态转移方程：

f[(x,y)][step] = f[(x-1,y)][step-1]+f[(x+1,y)][step-1]+f[(x,y-1)][step-1]+f[(x,y+1)][step-1]f[(x,y)][step]=f[(x−1,y)][step−1]+f[(x+1,y)][step−1]+f[(x,y−1)][step−1]+f[(x,y+1)][step−1]

注意，转移方程中 dp 数组的第一维存储的是 (x,y)(x,y) 对应的 idxidx。

从转移方程中我们发现，更新 f[i][j]f[i][j] 依赖于 f[x][j-1]f[x][j−1]，因此我们转移过程中需要将最大移动步数进行「从小到大」枚举。

至此，我们已经完成求解「路径规划」问题的两大步骤：「状态定义」&「转移方程」。

但这还不是所有，我们还需要一些 有效值 来滚动下去。

其实就是需要一些「有效值」作为初始化状态。

观察我们的「转移方程」可以发现，整个转移过程是一个累加过程，如果没有一些有效的状态（非零值）进行初始化的话，整个递推过程并没有意义。

那么哪些值可以作为成为初始化状态呢？

显然，当我们已经位于矩阵边缘的时候，我们可以一步跨出矩阵，这算作一条路径。

同时，由于我们能够往四个方向进行移动，因此不同的边缘格子会有不同数量的路径。

网络异常，图片无法展示

换句话说，我们需要先对边缘格子进行初始化操作，预处理每个边缘格子直接走出矩阵的路径数量。

目的是为了我们整个 DP 过程可以有效的递推下去。

可以发现，动态规划的实现，本质是将问题进行反向：原问题是让我们求从棋盘的特定位置出发，出界的路径数量。实现时，我们则是从边缘在状态出发，逐步推导回起点的出界路径数量为多少。

代码：

class Solution {
    int MOD = (int)1e9+7;
    int m, n, max;
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public int findPaths(int _m, int _n, int _max, int r, int c) {
        m = _m; n = _n; max = _max;
        int[][] f = new int[m * n][max + 1];
        // 初始化边缘格子的路径数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) add(i, j, f);
                if (j == 0) add(i, j, f);
                if (i == m - 1) add(i, j, f);
                if (j == n - 1) add(i, j, f);
            }
        }
        // 从小到大枚举「可移动步数」
        for (int k = 1; k <= max; k++) {
            // 枚举所有的「位置」
            for (int idx = 0; idx < m * n; idx++) {
                int[] info = parseIdx(idx);
                int x = info[0], y = info[1];
                for (int[] d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    int nidx = getIdx(nx, ny);
                    f[idx][k] += f[nidx][k - 1];
                    f[idx][k] %= MOD;
                }
            }
        }
        return f[getIdx(r, c)][max];       
    }
    void add(int x, int y, int[][] f) {
        for (int k = 1; k <= max; k++) {
            f[getIdx(x, y)][k]++;
        }
    }
    int getIdx(int x, int y) {
        return x * n + y;
    }
    int[] parseIdx(int idx) {
        return new int[]{idx / n, idx % n};
    }
}
复制代码