出界的路径数

题目

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

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

提示：

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

思路

定义dp[i][j][k]表示坐标(i,j),最多移动k次，出界的路径数。当k位于最中间，k<i,k<j,k<m-i,k<n-j。时，怎么都无法出界。直接返回0。状态转移方程为：dp[i][j][k] += dp[i+x][j+y][k-1],x=0、1或-1，y=0、1或-1。

代码

class Solution {
    vector<vector<vector<int>>> cache;
    int mod = 1000000007;
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        cache.assign(m,vector<vector<int>>(n,vector<int>(maxMove+1)));
        findUPaths(m, n, maxMove, startRow, startColumn);
        return cache[startRow][startColumn][maxMove];
    }
    int findUPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        
        if (maxMove < 0) {
            return 0;
        }

        if (maxMove < startRow && maxMove < m - startRow && maxMove < startColumn && maxMove < n - startColumn) {
            return 0;
        }

        if (startRow < 0 || startRow >= m || startColumn < 0 || startColumn >= n) {
            return 1;
        }

        if(cache[startRow][startColumn][maxMove] != 0) return cache[startRow][startColumn][maxMove];
        
        vector<vector<int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
        for(auto& direction: directions) {
            int row = startRow + direction[0];
            int column = startColumn + direction[1];
            cache[startRow][startColumn][maxMove] += findUPaths(m, n, maxMove-1, row, column);
            cache[startRow][startColumn][maxMove] %= mod;
        }
        return cache[startRow][startColumn][maxMove];
    }
};