## Nombre de chemins par mémoïsation


def chemins_memo(n: int, p: int) -> int:
    D = {}

    def chemins(i, j):
        if (i, j) in D:
            return D[(i, j)]
        elif i == 0 or j == 0:
            D[(i, j)] = 1
        else:
            D[(i, j)] = chemins(i-1, j) + chemins(i, j-1) + chemins(i-1, j-1)
        return D[(i, j)]

    return chemins(n, p)


print(chemins_memo(8, 10))
# 1256465
print(chemins_memo(20, 30))
# 386733690827821609


## Nombre de chemins : bottom_up

def chemins_bottom_up(n: int, p: int) -> int:
    D = {}

    for i in range(n+1):
        D[(i, 0)] = 1
    for j in range(p+1):
        D[(0, j)] = 1

    for i in range(1, n+1):
        for j in range(1, p+1):
            D[(i, j)] = D[(i-1, j)] + D[(i, j-1)] + D[(i-1, j-1)]

    return D[(n, p)]


print(chemins_bottom_up(8, 10))
# 1256465