menu

[LeetCode] 062. Unique Paths *

Problem (Medium)

062. 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 7 x 3 grid. 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

Approach 1: Dynamic Programming *

Idea

C++ DP - LeetCode

Since the robot can only move right and down, when it arrives at a point, it either arrives from left or above. If we use dp[i][j] for the number of unique paths to arrive at the point (i, j), then the state equation is dp[i][j] = dp[i][j - 1] + dp[i - 1][j]. Moreover, we have the base cases dp[0][j] = dp[i][0] = 1 for all valid i and j.

Solution

class Solution1:
    def uniquePaths(self, m, n): 
        """ 
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0 for _ in range(m)] for _ in range(n)]
        for i in range(m):
            dp[0][i] = 1 
        for j in range(n):
            dp[j][0] = 1 
        print(dp)
        for i in range(1, n): 
            for j in range(1, m): 
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

Complexity

  • Time: $O(mn)$
  • Space: $O(mn)$

Approach 2: Dynamic Programming Improved *

Idea

C++ DP - LeetCode

The above solution runs in O(m * n) time and costs O(m * n) space. However, you may have noticed that each time when we update dp[i][j], we only need dp[i - 1][j] (at the previous row) and dp[i][j - 1] (at the current row). So we can reduce the memory usage to just two rows (O(n)).

Solution

class Solution2:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        pre_row = [1 for i in range(m)]
        cur_row = [1 for i in range(m)]
        for i in range(1, n):
            for j in range(1, m):
                cur_row[j] = pre_row[j] + cur_row[j-1]
            cur_row, pre_row = pre_row, cur_row
        return pre_row[-1]

Complexity

  • Time: $O(mn)$
  • Space: $O(n)$



KF

Comments