Simple to understand Java DP Solution O(N*M)

  • 0

    Simple dynamic programming philosphy. Solutions build off of one another untill complete. Below you will notice an array called memo (as in memoization), it is an array that stores the results of a point in the grid so that you don't have to compute it again if you end up visting that point again. I like to view grids as (row x col) which is why n and m are switched but your free to switch it back and it will work.

    public class Solution {
        public int uniquePaths(int m, int n) {
            int[][] memo = new int[n+1][m+1];
            return pathHelper(n,m,1,1,memo);
        public int pathHelper(int rowMax, int colMax, int row, int col, int[][] memo){
            if(row > rowMax || col > colMax) return 0;
            if(row == rowMax && col == colMax) return 1;
            if(memo[row][col] == 0){
                memo[row][col] = pathHelper(rowMax, colMax, row+1,col,memo) + pathHelper(rowMax, colMax, row,col+1,memo);
            return memo[row][col];

Log in to reply

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