HJ91走方格的方案数（动态规划和递归解法）

Two solving methods:(动态规划和递归)
1.Dynamic programming,build route_array-like Yanghui_triangle,time complexity less than recursion,by observing we can get:a[i][j]=a[i-1][j]+a[i][j-1]
动态规划类似于杨辉三角，第0行和第0列的为1，这样通过矩阵的计算循环，规划出第[i][j]的值为该点左和上两个点的和，即为从[0][0]到[i][j]点的路径总数。
01-01-01-01-01-01.....
01-02-03-04-05-06.....
01-03-06-10-15-21.....
01-04-10-20-35-56.....
01-05-15-35-70-126....
......................
Code:

#dynamic programming
def dynamicp(m,n):
    road=[[0 for i in range(n)]]*m      #execute to create zero array
    for i in range(m):road[i][0]=1     #begin--row set to 1
    for j in range(n):road[0][j]=1     #begin--column set to 1
    for i in range(1,m):
        for j in range(1,n):
            road[i][j]=road[i-1][j]+road[i][j-1]
    return road[m-1][n-1]
while 1:
    try:
        s=list(map(int,input().split()))
        print(dynamicp(s[0]+1,s[1]+1))
    except:break

2.recursion: from digit-sheet above,we can get that:a[i][j]=a[i-1][j]+a[i][j-1]
递归：当m和n值较小时可以用该算法；
code:

def recursion(m,n):
    if m==0 or n==0:return 1
    else:return recursion(m-1, n)+recursion(m, n-1)
while 1:
    try:
        m,n=map(int,input().split())
        print(recursion(m, n))
    except:break