​LeetCode刷题实战576：出界的路径数

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 出界的路径数，我们先来看题面：

https://leetcode-cn.com/problems/out-of-boundary-paths/

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball. Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。

示例

解题

利用动态规划求解，假设球在第 t 步到达 (mi, nj) 位置有 dp[t][mi][nj] 种路径，我们可以想一下当前状态如何从上一步运动中得来。无非就是上下左右四个方向移动过来的，而移动步数是 t-1。

于是有转态转移方程：dp[t][mi][nj] = dp[t-1][mi-1][nj] + dp[t-1][mi][nj-1] + dp[t-1][mi+1][nj] + dp[t-1][mi][nj+1]

而初始状态下有 dp[0][i][j]=1。

具体实现时，为了避免边界判断，对二维网格上下左右都补 0，有 1<=mi<=m; 1<=ni<=n。

class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {
        if (N == 0) return 0;
        vector<vector<vector<long>>> dp(N, vector<vector<long>>(m+2, vector<long>(n+2)));
        dp[0][i+1][j+1] = 1;
        long res = 0;
        if (i == 0) res++;
        if (i == m-1) res++;
        if (j == 0) res++;
        if (j == n-1) res++;
        for (int t = 1; t < N; t++) {
            for (int mi = 1; mi <= m; mi++) {
                for (int nj = 1; nj <= n; nj++) {
                    dp[t][mi][nj] = (dp[t-1][mi-1][nj] + dp[t-1][mi+1][nj] + dp[t-1][mi][nj-1] + dp[t-1][mi][nj+1]) % 1000000007;
                    if (mi == 1) res += dp[t][mi][nj];
                    if (mi == m) res += dp[t][mi][nj];
                    if (nj == 1) res += dp[t][mi][nj];
                    if (nj == n) res += dp[t][mi][nj];
                    res %= 1000000007;
                }
            }
        }
        return int(res);
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-560题汇总，希望对你有点帮助！

LeetCode刷题实战561：数组拆分 I

LeetCode刷题实战562：矩阵中最长的连续1线段

LeetCode刷题实战563：二叉树的坡度

LeetCode刷题实战564：寻找最近的回文数

LeetCode刷题实战565：数组嵌套

LeetCode刷题实战566：重塑矩阵

LeetCode刷题实战567：字符串的排列

LeetCode刷题实战568：最大休假天数

LeetCode刷题实战569：员工薪水中位数

LeetCode刷题实战570：至少有5名直接下属的经理

LeetCode刷题实战571：给定数字的频率查询中位数

LeetCode刷题实战572：另一棵树的子树

LeetCode刷题实战573：松鼠模拟

LeetCode刷题实战574：当选者

LeetCode刷题实战575：分糖果