0062.py

# Source: https://leetcode.com/problems/unique-paths
# Title: Unique Paths
# Difficulty: Medium
# Author: Mu Yang <http://muyang.pro>

################################################################################################################################
# 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 * 10^9.
#
# Example 1:
#
#   https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png
#   Input: m = 3, n = 7
#   Output: 28
#
# Example 2:
#
#   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 -> Down -> Down
#     2. Down -> Down -> Right
#     3. Down -> Right -> Down
#
# Constraints:
#
#   1 <= m, n <= 100
#
################################################################################################################################

# Python 3.8+
from math import comb
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m+n-2, m-1)

################################################################################################################################

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        res = 1
        if m > n:
            m, n = n, m
        m -= 1
        n -= 1

        # C^{m+n}_m
        for i in range(m):
            res *= n+m-i
            res /= (i+1)

        return int(res)