给你一个大小为 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

示例 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

动态规划

class Solution {
public:int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {int MOD = 1e9 + 7;vector<vector<int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};int outcounts = 0;vector<vector<vector<int>>> dp(maxMove+1, vector<vector<int>>(m, vector<int>(n)));dp[0][startRow][startColumn] = 1;for(int i = 0; i < maxMove; i++){for(int j = 0; j < m; j++){for(int k = 0; k < n; k++){int count = dp[i][j][k];if(count > 0){for(auto direction : directions){int j1 = j + direction[0], k1 = k + direction[1];if(j1 >= 0 && j1 < m && k1 >= 0 && k1 < n){dp[i+1][j1][k1] = (dp[i+1][j1][k1] + count) % MOD;}else{outcounts = (outcounts + count) % MOD;}         }}}}}return outcounts;}
};

这道题可以定义一个三维数组dp[i][j][k]用来表示走了i步后落在位置(j,k)的路径总数。我们需要知道的一点是，当我们确定了第i步落在了(j,k)，那么第i+1步有可能是向上向下向左向右四种方向，对应到不同的位置。如果(j1,k1)在界内，那么我们可以定义一个directions来计算第i+1步向四个不同方向走后的状态转移方程dp[i+1][j1][k1] = (dp[i+1][j1][k1] + count) % MOD;，count是dp[i][j][k]，j1和k1是第i+1步后落的位置。如果j1和k1在界外，那么就记录到出界的路径数outcounts中。

注：由于i+1只由i转移而来，可以压缩dp[i][j][k]为dp[j][k]，进行空间优化。