unique_path

  • 2022-12-14
  • 浏览 (564)

unique_path.py 源码

# 不同路径


# 使用分治的思想,递归解决
def unique_path_1(m: int, n: int) -> int:
    def helper(a, b, i, j) -> int:
        if i == a and j == b:
            return 1
        x, y = 0, 0
        if i < a:
            x = helper(a, b, i + 1, j)
        if j < b:
            y = helper(a, b, i, j + 1)
        return x + y

    return helper(m, n, 1, 1)


# 动态规划的思路解决
def unique_path_2(m: int, n: int) -> int:
    # dp = [[1 for _ in range(n)] for _ in range(m)]
    dp = [[1] * n] * m
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[-1][-1]


# 简化一维的写法
def unique_path_3(m: int, n: int) -> int:
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[-1]

你可能感兴趣的文章

coin_change

decode_ways

edit_distance

0  赞