🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

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?

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3:
Input: m = 7, n = 3
Output: 28

Example 4:
Input: m = 3, n = 3
Output: 6

Solution:

The chapter on Counting DP explains the approach we have implemented in the code below. Keep in mind that for this problem: number of ways of reaching a cell in one hop = 2 (from left cell and from cell above), since robot can move only in down and right directions.

I have discussed the algorithm and implementation logic in details in the inline comments in code below:

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Track Path:

Track Path = Keep Parent Pointers and then do DFS. While doing DFS keep a list to track current path.

When we reach source (0, 0) as part of a DFS path, we print the current path. When DFS has been done for a node completely, we remove that node from the list so that the node does not appear in a path it is not part of.
Unlike traditional DFS, here we traverse a visited node more than once if needed since our objective is to print all valid paths.

In most cases path can be tracked using this same approach. Even when there is only one path instead of multiple, that one path can also be thought of as a tree, and we should be able to do DFS on it.

Read the inline comments in the code for more details.

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Space Optimization:

Notice in the previous code that we are filling up the memo row by row as we go down. For any cell we need the value of the cell left to the current cell in the same row and the cell above the current cell in the row above the current row. So while processing cells of row i we only need previously computed values of row i - 1 and just computed values in row i. We will use this observation to optimize space. I have put more details in the inline comments in the code below.

Java code:

Login to Access Content

Python Code:

Login to Access Content

Track Path:

We will track path for the Space Optimized solution in the same way we have done before:

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Instructor: