题解 | #不同路径的数目(一)#

def multiply_strings(num1, num2):
    # 辅助函数：两个大数字符串的乘法
    result = [0] * (len(num1) + len(num2))
    
    for i in range(len(num1) - 1, -1, -1):
        carry = 0
        for j in range(len(num2) - 1, -1, -1):
            temp = int(num1[i]) * int(num2[j]) + carry + result[i + j + 1]
            carry = temp // 10
            result[i + j + 1] = temp % 10
        result[i] += carry
    
    return "".join(map(str, result)).lstrip("0") or "0"

def factorial(num):
    # 计算大数阶乘
    result = "1"
    for i in range(2, num + 1):
        result = multiply_strings(result, str(i))
    
    return result

def nCr(n, r):
    # 计算大数组合数 C(n, r) = n! / (r! * (n-r)!)
    if r == 0 or r == n:
        return "1"
    
    numerator = factorial(n)
    denominator = multiply_strings(factorial(r), factorial(n - r))
    return str(int(numerator) // int(denominator))

def nPr(n, r):
    # 计算大数排列数 P(n, r) = n! / (n-r)!
    if r == 0:
        return "1"
    
    numerator = factorial(n)
    denominator = factorial(n - r)
    return str(int(numerator) // int(denominator))


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

        else:
            x = nCr(m+n-2,n-1)
            x = int(x)
            return x