Java solution DP


  • 0
    public class Solution {
           int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
           int MODE = 1000000007;
        public int findPaths(int m, int n, int N, int i, int j) {
            HashMap<Integer, Integer>[][] memo = new HashMap[m][n];
              return findPathsHelper(m,n,i,j,N,memo);
           
        }
        
        public int findPathsHelper(int m, int n, int i, int j, int N, HashMap<Integer, Integer>[][] memo){
            if(i<0 || i >=m || j<0 || j>=n) return 1;
            if(N==0) return 0 ;
            if(memo[i][j] != null && memo[i][j].containsKey(N)) return memo[i][j].get(N);
            int sum=0;
            long temp=0;
            for(int[] dir : dirs){
                int x= dir[0]+i;
                int y =dir[1]+j;
               temp += findPathsHelper(m,n,x,y,N-1, memo);
            }
            sum =(int) (temp%MODE);
            if(memo[i][j]==null){
                memo[i][j] = new HashMap();
                memo[i][j].put(N, sum);
            }
            memo[i][j].put(N, sum);
            return sum;
        }
        
        
    }
    

Log in to reply
 

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