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
- 示例 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
解題思路
數組定義
數組定義dp[i][j]為到達[i][j]時可能的路徑數量，因為每一步dp[i][j]的路徑數量只和上一步有關，因此我們可以用滾動數組的方法來迭代
狀態轉移
每個格子可以向其他四個方向移動，所以需要將當前位置的路徑數量累加到周圍的4個格子，如果移出了邊界，則累加進入數組
初始化
球的起始坐標為 [startRow, startColumn] 路徑數量置為1
代碼
class Solution {public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int[][] dp = new int[m][n];int res=0,mod=1000000007;dp[startRow][startColumn]=1;for (int i=0;i<maxMove;i++){int[][] newDp = new int[m][n];for (int k=0;k<m;k++)for (int j=0;j<n;j++){int old=dp[k][j];if (old>0){for (int[] d : dir) {int r=d[0]+k,c=d[1]+j;if (r>=0&&r<m&&c>=0&&c<n){newDp[r][c]=(old+newDp[r][c])%mod;}else{res=(res+old)%mod;}}}}dp=newDp;}return res;}
}
時間復雜度：O(maxMove×m×n)。動態規劃需要遍歷的狀態數是 O(maxMove×m×n)，對于每個狀態，計算后續狀態以及出界的路徑數的時間都是O(1)。
空間復雜度：O(m×n)。使用空間優化的實現，空間復雜度是 O(m×n)。
