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 = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right Example #2
Input: m = 7, n = 3 Output: 28 First thought that might came to mind is that we need to build a decision tree where D means moving down and R means moving right. For example in case of boars width = 3 and height = 2 we will have the following decision tree:
START / \ D R / / \ R D R / / \ R R D END END END We can see three unique branches here that is the answer to our problem.
Time Complexity: O(2 ^ n) - roughly in worst case with square board of size n.
Auxiliary Space Complexity: O(m + n) - since we need to store current path with positions.
Let's treat BOARD[i][j] as our sub-problem.
Since we have restriction of moving only to the right and down we might say that number of unique paths to the current cell is a sum of numbers of unique paths to the cell above the current one and to the cell to the left of current one.
BOARD[i][j] = BOARD[i - 1][j] + BOARD[i][j - 1]; // since we can only move down or right. Base cases are:
BOARD[0][any] = 1; // only one way to reach any top slot. BOARD[any][0] = 1; // only one way to reach any slot in the leftmost column. For the board 3 x 2 our dynamic programming matrix will look like:
| 0 | 1 | 1 | |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 1 | 1 | 2 | 3 |
Each cell contains the number of unique paths to it. We need the bottom right one with number 3.
Time Complexity: O(m * n) - since we're going through each cell of the DP matrix.
Auxiliary Space Complexity: O(m * n) - since we need to have DP matrix.
This question is actually another form of Pascal Triangle.
The corner of this rectangle is at m + n - 2 line, and at min(m, n) - 1 position of the Pascal's Triangle.
