Java - Unoptimized Top-Down Approach


  • 0
    Y

    This is an unoptimized solution, but easy to understand.

    class Solution {
        public int uniquePaths(int N, int M) {
            int [][]mem = new int[N][M];
            init(mem);
            return countUniquePaths(N,M,0,0,mem);
        }  
        private void init(int[][] mem) {
    		for (int i = 0 ; i < mem.length ; i++) {
    			for (int j = 0 ; j < mem[0].length ; j++) {
    				mem[i][j] = -1;
    			}
    		}
    	}
        
        public int countUniquePaths ( int N,int M,int i , int j , int[][]mem) {
          if (i < 0 || i >= N || j<0 || j>= M) return 0;
          if (i == N-1 && j == M-1) return 1;
          if (mem[i][j] !=-1) return mem[i][j];
          int ret  = countUniquePaths(N,M,i,j+1,mem) + countUniquePaths(N,M,i+1, j, mem) ;
          mem[i][j] = ret;
          return ret;
      }
    }
    

Log in to reply
 

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