Compter les chemins dans une grille

Soit $N(i,j)$ le nombre de chemins menant à la case $(i,j)$. On a $N(i,j)=N(i-1,j)+N(i,j-1)$, avec $N(0,j)=N(i,0)=1$ (une seule façon de longer un bord).

def chemins_grille(m, n):
    table = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            table[i][j] = table[i - 1][j] + table[i][j - 1]
    return table[m - 1][n - 1]

La complexité est $O(m\times n)$.