51Nod-1118-機器人走方格

51Nod-1118-機器人走方格

1118 機器人走方格

M * N的方格，一個機器人從左上走到右下，隻能向右或向下走。有多少種不同的走法？
由于方法數量可能很大，隻需要輸出Mod 10^9 + 7的結果。

Input
第1行，2個數M,N，中間用空格隔開。（2 <= m,n <= 1000)

Output
輸出走法的數量。

Input示例
2 3
Output示例
3
           

解題方法

這是一道基礎的動态規劃題目。

每次到某個格子的走法都是它的前兩個格子，即它上方格子和左方格子的走法數量之和。

那麼定義子問題f(i, j)為

坐标為（i，j）時候的走法。

那麼也就得出了狀态轉移公式：

f(i, j) = f(i-1, j)+f(i, j-1)

同時 定義第一個格子的走法為1，即f(0,0)=1。

解題代碼

while True:
    try:
        n, m = list(map(int, input().split()))
        Mod = ** + 
        f = [ [ for i in range(m+)] for j in range(n+)]

        pre = [[-1,0], [0,-1]]
        f[][] = 
        for i in range(n):
            for j in range(m):
                for k in range():
                    tx = i + pre[k][]
                    ty = j + pre[k][]
                    if tx <  or ty <:
                        continue
                    f[i][j] = (f[tx][ty] + f[i][j])%Mod


        print((f[n-][m-])%Mod)
    except EOFError:
        break