LC 576. 出界的路径数

题目描述

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

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

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

你最多可以移动 maxMove 次球。

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

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

示例 1：

1
2
3

输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0

输出：6

示例 2：

1
2
3

输入：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 函数来解决本题，你会如何设计？

我大概会这样设计：

1	`int dfs(int x, int y, int k) {}`

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

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

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

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

Java 代码：

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;
    }
}

C++ 代码：

class Solution {
public:
    int MOD = 1e9 + 7;
    int m, n, max;
    vector<vector<vector<int>>> cache;
    vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int findPaths(int _m, int _n, int _max, int r, int c) {
        m = _m; n = _n; max = _max;
        cache = vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(max + 1, -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 (auto& 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[][]$ 作为我们的 dp 数组：

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

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

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

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

至此，我们只是根据「记忆化搜索」中的 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]$

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

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

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

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

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

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

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

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

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

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

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

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

Java 代码：

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};
    }
}

C++ 代码：

class Solution {
public:
    int MOD = 1e9 + 7;
    int m, n, max;
    vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int findPaths(int _m, int _n, int _max, int r, int c) {
        m = _m; n = _n; max = _max;
        vector<vector<int>> f(m * n, vector<int>(max + 1, 0));
        // 初始化边缘格子的路径数量
        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++) {
                pair<int, int> info = parseIdx(idx);
                int x = info.first, y = info.second;
                for (auto& d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        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, vector<vector<int>>& f) {
        for (int k = 1; k <= max; k++) {
            f[getIdx(x, y)][k]++;
        }
    }
    int getIdx(int x, int y) {
        return x * n + y;
    }
    pair<int, int> parseIdx(int idx) {
        return {idx / n, idx % n};
    }
};

时间复杂度：共有 $m \times n \times max$ 个状态需要转移，复杂度为 $O(m \times n \times max)$
空间复杂度：$O(m \times n \times max)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.576 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

动态规划记忆化搜索路径 DP

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 526. 优美的排列上一篇

LC 1583. 统计不开心的朋友下一篇