62. Unique Paths

Problem Statement

link: https://leetcode.com/problems/unique-paths/ https://leetcode.cn/problems/unique-paths/

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example:

Input: m = 3, n = 7 Output: 28

Input: m = 3, n = 2 Output: 3

Solution Approach

The problem can be solved using dynamic programming by leveraging the fact that the number of unique paths to any cell is the sum of paths from its left and top cells.

Algorithm

1. Initialize a matrix with the first row and column set to ones, representing single paths.
2. For each cell starting from the second row and column, sum the values from its top and left neighbors.
3. The bottom-right cell contains the total unique paths from the top-left corner.

Implement

    class Solution:
      def uniquePaths(self, m: int, n: int) -> int:
      matrix = [[0] * n for _ in range(m)]
      for i in range(m):
          for j in range(n):
              if i == 0 or j == 0:
                  matrix[i][j] = 1
              else:
                  matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]
      return matrix[m - 1][n - 1]
      

    
    

Twitter  facebook  Email