576. 出界的路径数

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

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

示例 1：

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

提示：

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

方法一: dfs

不用标记位置.
相同的出口位置,不同的步数也算不同的方案

class Solution {
public:
    const int MOD = 1e9 + 7;
    int dir[4][2]={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int ans= 0;
    int u[55][55];
    int mm, nn;
    void dfs(int i, int j, int step, int maxMove) {
        if(step >= maxMove) return;
        for(int k = 0; k < 4; k++) {
            int x = i + dir[k][0], y = j + dir[k][1];
            if(x < 0 || x >= mm || y < 0 || y >= nn) {
                ans++;
                ans %= MOD;
                continue ;
            }else {
                dfs(x, y, step + 1, maxMove);
            }
        }
    }
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        mm = m, nn =n;
        dfs(startRow, startColumn, 0, maxMove);
        return ans;
    }
};

• 最后还是超时了,

方法二:记忆化搜索 | 动态规划

上面分析到,相同的位置可能有多种方案,当方案走到i,j,k(位置+步数)时可以记录下来,下次遍历到直接加起来就可以
记忆化搜索联系最紧的就是动态规划,把步数再加一个状态->dp[i][j][k],就表示i,j位置,用了k步的方案数

class Solution {
public:
    int dp[55][55][55];
    const int MOD = 1e9 + 7;
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        //初始化的时候四周有一种方案,角有两种,需要预处理
        for(int k = 1; k <= maxMove; k++) {
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(i == 0) dp[i][j][k]++;
                    if(j == 0) dp[i][j][k]++;
                    if(i == m -1) dp[i][j][k]++;
                    if(j == n -1) dp[i][j][k]++;
                    for(auto h : dir) {
                        int x = i + h[0], y = j + h[1];
                        if(!(x < 0 || x >= m || y < 0 || y >= n)){
                            dp[i][j][k] = (dp[i][j][k] + dp[x][y][k - 1]) % MOD;
                        }
                    }
                }
            }
        } 
        return dp[startRow][startColumn][maxMove];
    }
};