Problem: Grid Unique Paths
A robot is located at the top-left corner of an A x B grid.
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, from the upper-left corner.
How many possible unique paths are there?
Note: A and B will be such that the resulting answer fits in a 32 bit signed integer.
Input : A = 2, B = 2 Output : 2 2 possible routes : (0, 0) -> (0, 1) -> (1, 1) OR : (0, 0) -> (1, 0) -> (1, 1)
We can solve it using dynamic programming, as we can see that for any position, in the first row and the first column, the only answer is 1.
Say, dp[j] = dp[i] = 1, where, 0<=i<A & 0<=j<B
And for every other position say (i,j), the answer would be,
dp[i][j] = dp[i-1][j] + dp[i][j-1]
Because we can only move either down or right, so number of possible ways to reach a any given position, would be the sum of ways to rich its upper and left position.
You can see that to reach bottom-right from top-left, you have to take N + M - 2 steps.
Where N is the number of rows & M is the number of columns.
The above statement is true because you can move only down and right, so to reach the last column you must take M - 1 steps, and to reach the last row you must take N - 1 steps. So you have to take total of N + M - 2 steps.
Since you have to take M - 1 steps of right move, in total of N + M - 2 steps. Therefore, we have to choose the M - 1 from N + M - 2.
(N+M-2)C(M-1) = (N+M-2)! / (N-1)! (M-1)!
Time & Space Complexity:
Time Complexity: O(N^2) Space Complexity: O(N^2)
Time Complexity: O(N) Space Complexity: O(1)
Method 1: Code in C++
Method 2: Code in C++