Unique Paths

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?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

This is also EPI 17.4. Number of Ways.

Location:  P403. Elements of Programming Interviews

Idea:

Here is an example: m =5, n =5

The number of ways to get from (0; 0) to (i; j) for 0 <= i <= 4;  0 <= j <=  4.

Solution 1:

1 class Solution:2     # @return an integer3     def uniquePaths(self, m, n):4         f = [[1 for i in range(n)] for i in range(m)]5         for i in range(1,m):6             for j in range(1,n):7                 f[i][j] = f[i-1][j] + f[i][j-1]8         return f[-1][-1]

time complexity is: O(mn)
space complexity is: O(nm)

Solution 2:

 1 class Solution: 2     # @return an integer 3     def uniquePaths(self, m, n): 4         if n < m: m, n = n, m 5         f = [1] * m 6         for i in range(1, n): 7             prev_res = 0 8             for j in range(m): 9                 f[j] = f[j] + prev_res10                 prev_res = f[j]11         return f[-1]

time complexity is: O(mn)
space complexity is: O(min(m, n))

Unique Paths @ Python Leetcode EPI 17.4