62.md

题目地址

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

解答1

def uniquePaths(m, n):
    """
        不同路径

        输入: m = 3, n = 2
        输出: 3
        解释:
        从左上角开始，总共有 3 条路径可以到达右下角。
        1. 向右 -> 向右 -> 向下
        2. 向右 -> 向下 -> 向右
        3. 向下 -> 向右 -> 向右
    """
    return combination(m + n - 2, n - 1)


def combination(n, m):
    """ 计算组合C(n, m) """
    return factorial(n) // factorial(m) // factorial(n - m)

解答2

def uniquePaths(m, n):
    """
        不同路径

        输入: m = 3, n = 2
        输出: 3
        解释:
        从左上角开始，总共有 3 条路径可以到达右下角。
        1. 向右 -> 向右 -> 向下
        2. 向右 -> 向下 -> 向右
        3. 向下 -> 向右 -> 向右
    """
    res = [[1] * m] + [[1] + [0] * (m - 1)] * (n - 1)
    for i in range(1, n):
        for j in range(1, m):
            res[i][j] = res[i - 1][j] + res[i][j - 1]

    return res[n - 1][m - 1]