Java Solution, DP with space compression


  • 18

    DP[i][j][k] stands for how many possible ways to walk into cell j,k in step i, DP[i][j][k] only depends on DP[i - 1][j][k], so we can compress 3 dimensional dp array to 2 dimensional.

    public class Solution {
        public int findPaths(int m, int n, int N, int i, int j) {
            if (N <= 0) return 0;
            
            final int MOD = 1000000007;
            int[][] count = new int[m][n];
            count[i][j] = 1;
            int result = 0;
            
            int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            
            for (int step = 0; step < N; step++) {
                int[][] temp = new int[m][n];
                for (int r = 0; r < m; r++) {
                    for (int c = 0; c < n; c++) {
                        for (int[] d : dirs) {
                            int nr = r + d[0];
                            int nc = c + d[1];
                            if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                                result = (result + count[r][c]) % MOD;
                            }
                            else {
                                temp[nr][nc] = (temp[nr][nc] + count[r][c]) % MOD;
                            }
                        }
                    }
                }
                count = temp;
            }
            
            return result;
        }
    }
    

  • 0
    T
    This post is deleted!

  • 0
    T

    Great Solution! I emulate your method!

    public class Solution {
        public int findPaths(int m, int n, int N, int i, int j) {
            int res=0;
            if(N<=0) return 0;
            
            int[][] dp=new int[m][n];
            int[][] dirs=new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
            
            for(int[] ele:dirs){
                int x=ele[0]+i;
                int y=ele[1]+j;
                if(x<0||x>=m||y<0||y>=n){
                    res++;
                }else{
                    dp[x][y]=1;
                }
            }
            
            if(N==1){
                return res;
            }
            
            int max=1000000007;
            for(int p=2;p<=N;p++){
                int[][] temp=new int[m][n];
                for(int k=0;k<m;k++){
                    for(int q=0;q<n;q++){
                        for(int[] dir:dirs){
                           int x = dir[0]+k;
                           int y = dir[1]+q;
                           
                           if(x<0||x>=m||y<0||y>=n){
                               res=(res+dp[k][q])%max;
                           }else{
                               temp[x][y]=(temp[x][y]+dp[k][q])%max;
                           }
                       } 
                    }
                }
                
                dp=temp;
            }
            
            
            return res;
        }
    }
    

  • 1

    I like this method best. Each N is the sum of N-1 from four directions


  • 0
    H

    Brilliant and concise!
    temp[][] stores the k-th move while count[][] stores the k-1 th.


Log in to reply
 

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