Unique paths in Grid

Problem: 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?

Algo:
1. Maintain one more stack to store minimum elements (minimum stack).
2. To retrieve the current minimum, just return the top element from minimum stack.
3. Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack too.
4. When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum stack too.

Backtracking Solution:

The most direct way is to write code that traverses each possible path, which can be done using backtracking. When you reach row=m and col=n, you know you’ve reached the bottom-right corner, and there is one additional unique path to it. However, when you reach row>m or col>n, then it’s an invalid path and you should stop traversing. For any grid at row=r and col=c, you have two choices: Traverse to the right or traverse to the bottom. Therefore, the total unique paths at grid (r,c) is equal to the sum of total unique paths from the grid to the right and the grid below. Below is the backtracking code in 5 lines of code:

1 2 3 4 5 6 7 8

int backtrack(int r, int c, int m, int n) {   if (r == m && c == n)     return 1;   if (r > m || c > n)     return 0;      return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n); }

Dynamic Programming Solution using Bottom-up Approach:
If you notice closely, the above DP solution is using a top-down approach. Now let’s try a bottom-up approach. Remember this important relationship that is necessary for this DP solution to work:

The total unique paths at grid (r,c) is equal to the sum of total unique paths from grid to the right (r,c+1) and the grid below (r+1,c).

How can this relationship help us solve the problem? We observe that all grids of the bottom edge and right edge must all have only one unique path to the bottom-right corner. Using this as the base case, we can build our way up to our solution at grid (1,1) using the relationship above.

1 2 3 4 5 6 7 8 9 10 11

int dp(int[][] mat, int m, int n) {     mat[m-1][n] = 1   mat[m][n-1] = 1;      for (int r = m-1; r >= 1; r--)     for (int c = n-1; c >= 1; c--)       mat[r][c] = mat[r+1][c] + mat[r][c+1];      return mat[0][0]; }