LeetCode Out of Boundary Paths

· 610 words · 2 minute read
2017年8月
LeetCode-动态规划

576. Out of Boundary Paths

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1:

Input:m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:

Example 2:

Input:m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:

Note:

  1. Once you move the ball out of boundary, you cannot move it back.
  2. The length and height of the grid is in range [1,50].
  3. N is in range [0,50].

方法

首先想着直接递归求解，超时…

public class Solution {
    public int findPaths(int m, int n, int N, int i, int j) {
        int[][] grid = new int[m][n];
        return find(grid,i+1,j,0,N) + find(grid,i-1,j,0,N) + find(grid,i,j+1,0,N) + find(grid,i,j-1,0,N);
    }
    public int find(int[][] grid, int i, int j, int n, int N){
        int count = 0;
        if(n >= N){
            return count;
        }
        if(n < N){
            if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length){
                count++;
                return count;
            }
        }
        count = find(grid,i+1,j,n+1,N) + find(grid,i-1,j,n+1,N) + find(grid,i,j+1,n+1,N) + find(grid,i,j-1,n+1,N);
        return count;
    }
}

转而使用DP。这道题给了我们一个很好的关于三维dp数组的例子。一般来说，对于矩阵，二维dp数组足以。但是在矩阵中附加了某些条件，比如限定走的次数等等，由于下次走跟这一次走有关系，所以又多了一维，故为三维。

总结，在二维数组下添加了某些限制，则变为三维数组，且该限制在第一维

该解本人有一点不理解，就是为什么要声明为long,int的大小大于10^9+7，但是若为int,则会报错，long强转为int后却success。知道了！！！假设四个数分别为1000000000，那么相加为4000000000，超出int，所以必须为long

public class Solution {
    public int findPaths(int m, int n, int N, int i, int j) {
        long[][][] dp = new long[N+1][m][n];
        for(int step = 1; step <= N; step++){
            for(int row = 0; row < m; row++){
                for(int p = 0; p < n; p++){
                    dp[step][row][p] = (((row == 0) ? 1 : dp[step-1][row-1][p])
                                        + ((row == m-1) ? 1 : dp[step-1][row+1][p])
                                        + ((p == 0) ? 1 : dp[step-1][row][p-1])
                                        + ((p == n-1) ? 1 : dp[step-1][row][p+1]))%1000000007;
               }
            }
        }
        return (int)dp[N][i][j];
    }
}
Share