DFS with DP method, 12ms, beat, 100%


  • 0
    M

    The dfs with dp method is very clear. I'm surprised to the running time.

    PS: At first, it always output wrong answer, but I think this method is very clear and naive. Then I realized that in the problem description, it said that "The answer may be very large, return it after mod 10^9 + 7." So just put a mod 10^9 + 7 for count.

    class Solution {
        public int findPaths(int m, int n, int N, int i, int j) {
            int[][][] mat = new int[m][n][N+1];
            int count = dfs(mat, i, j, N) % 1000000007;
            return count;
        }
        
        private final static int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        
        private int dfs(int[][][] mat, int x, int y, int step){
            if(x<0 || y<0 || x>=mat.length || y>=mat[0].length) return 1;
            if (x-step>=0 && x+step<mat.length && y-step>=0 && y+step<mat[0].length)  return 0;
            if(step<=0) return 0;
            if(mat[x][y][step]>0) return mat[x][y][step];
            int count = 0;
            for(int[] dir : dirs){
                int i = x + dir[0];
                int j = y + dir[1];
                count += dfs(mat, i, j, step-1);
                count %= 1000000007;
            }
            mat[x][y][step] = count;
            return count;
        }
    }
    

    I think running time in the worst case is O(mnN).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.