算法——m*n方格从左上角到右下角走法

m*n的方格，从左上角开始出发，只能向右走或向下走，一共有多少种走法?

(1)动态规划

import numpy as np
def left_to_right(m,n):
    d=np.zeros(dtype=int,shape=(m,n))
    d[0][0]=0
    for i in range(1,m):
        d[i][0]=1
    for j in range(1,n):
        d[0][j]=1
    for i in range(1,m):
        for j in range(1,n):
            d[i][j]=d[i-1][j]+d[i][j-1]
    return d[m-1][n-1]
if __name__=='__main__':
    res=left_to_right(7,5)
    print res

 

(2)排列组合

走完一共会走m+n步，利用排列组合的方法，C（n,m+n）或C（m,m+n）