576. Out of Boundary Paths

Link

Solution

最直接的辦法針對每個方向做dfs，若出界就count +1 直到最後 step用完為止。

int count = 0;
    public int findPaths(int m, int n, int N, int i, int j) {
        
        dfs(m, n, N, i, j);
        return count;
    }
    
    public void dfs(int m, int n, int N, int i, int j){        
        if(i < 0 || i >= m || j < 0 || j >= n){
            count = (count + 1) % (int)(1e9+7);
            return;
        }
        if(N == 0) return;
        
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int[] dir : dirs){
            int x = i + dir[0];
            int y = j + dir[1];
            dfs(m, n, N-1, x, y);
        }
    }

但是這個會有performace issue，原因是recheck了許多重複的事件。

例如: 先上在右， 跟先右在上，會被重複check。

所以用memorization去處理

T: O(m*n*N), just fill the content of the array

  public int findPaths(int m, int n, int N, int i, int j) {
        int[][][] memory = new int[m][n][N+1];
        for(int row = 0; row < m; row++){
            for(int col = 0; col < n; col++){
                for(int step = 1; step < N+1; step++){
                    memory[row][col][step] = -1;
                }
            }
        }
        
        return dfs(m, n, N, i, j, memory) % (int)(1e9+7);
    }
    
    public int dfs(int m, int n, int N, int i, int j, int[][][] memory){        
        if(i < 0 || i >= m || j < 0 || j >= n){
            return 1;
        }
        if(N == 0) return 0;
        
        if(memory[i][j][N] != -1) return memory[i][j][N]; 
        
        memory[i][j][N] = 0;
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int[] dir : dirs){
            int x = i + dir[0];
            int y = j + dir[1];
            memory[i][j][N] = (memory[i][j][N] + dfs(m, n, N-1, x, y, memory)) % ((int)(1e9+7));
        }
        return memory[i][j][N];
        
    }