• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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 target = 2 (from left cell and from cell above), since robot can move only in down and right directions.



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




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.



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




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.



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Track Path:


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


This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave