Unique Paths Problem

Question

A robot is located at the top-left corner of a m x n 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 (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

Constraints:

• 1 <= m, n <= 100
• It's guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

Answer 1

We will apply dyanmic programming here to explore what all ways can be reached from every point in the array.

One way to solve this problem is to use dynamic programming: define by dp[i][j] number of ways to reach point (i,j). How can we reach it, there are two options:

1. We can reach it from above (i, j-1).
2. We can reach it from the left: (i-1, j).
3. That is all! We just evaluate dp[i][j] = dp[i-1][j] + dp[i][j-1]
4. Complexity: time comlexity is O(mn), space complexity is O(mn), which can be improved to O(min(m,n)).
    

class Solution(object):     def uniquePaths(self, m, n):         """         :type m: int         :type n: int         :rtype: int         """         #### DP solution ####                  # edge cases         if m <= 0 or n <= 0:             return 0         if m == 1 or n == 1:             return 1                 # build an empty matrix         matrix = [[1 for j in range(n)]for i in range(m)]                  # record steps for each cell using DP (Expect the first row and the first column, since there are only one way to get the cells in these places..)         for i in range(1,m):             for j in range(1,n):                 matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]         return matrix[-1][-1]

To run the code :

path  = Solution()
path.uniquePaths(3,2)

Output : 
3