Understanding dynamic programming through a example

Viewed 268

I have just started learning dp and trying to solve this problem from leetcode using the same ( https://leetcode.com/problems/unique-paths/)

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

enter image description here

Here is what I tried:

public class Solution {
public int uniquePaths(int m, int n) {
    int [][] grid = new int[m][n];
    int [][] memo = new int[m][n];
    return uniquePathsHelper(grid,m,n,memo);
}

public int uniquePathsHelper(int [][] grid, int row,int col,int[][]memo){
    if(row>grid.length-1 || col>grid[0].length-1) return -1;
    if(row == grid.length-1 && col == grid[0].length-1) return 0;
    if(memo[row][col]!=0) return memo[row][col];

    if(col == grid[0].length-1) memo[row][col] = uniquePathsHelper(grid,row+1,col,memo)+1;
    if(row == grid.length-1) memo[row][col] = uniquePathsHelper(grid,row,col+1,memo)+1;
    // int rowInc = Integer.MIN_VALUE;
    // int colInc = Integer.MIN_VALUE;
    // if(row<grid.length-1) rowInc =  uniquePathsHelper(grid, row+1,col,memo);
    // if(col<grid.length-1) colInc = uniquePathsHelper(grid,row,col+1,memo);


    // if(row == grid.length-1 || col == grid[0].length-1) return 1;

    // if(row<grid.length-1) return 2;
    // if(col<grid[0].length-1) return 2;

    if(col< grid[0].length-1 && row < grid.length-1) memo[row][col] = memo[row+1][col] + memo[row][col+1];
    System.out.println("Memo["+row+"]["+col+"] = "+memo[row][col]);
    return memo[0][0];
    }
}

Sorry if this sounds very basic, I know I am missing something. Can anyone point out what is wrong with it?

1 Answers
Related