题解 | #走方格的方案数#

法1：
递归
一开始，有2个选择：

1. 往下，剩下的路，有f(n-1,m)种走法
2. 往右，剩下的路，有f(n,m-1)种走法

法2：
到了第c-1列，除了在最底行的情况，都有2种走法，往右或往左，所以我一开始以为 f(r,c)=f(r,c-1)+r
但在第_r行,不是多了一种走法，而是多了f(_r,c-1)种，所以是：
f(r,c)=f(r,c-1)+f(r-1,c-1)+f(r-2,c-1)+...+f(1,c-1)+1

import sys
def f(r,c):

    if  c==1:
        return r+1
    else:
        l=[1]
        for i in range(1,r+1):
            l .append(f(i,c-1))
        return sum(l) 
for line in sys.stdin:
    l=line.strip().split(' ')
    _r,_c=int(l[0]),int(l[1])
    print(f(_r,_c))

法3:
只要往右和左的步数分别达到n，m, 就能到右下角的终点。
记往右为1，往下为0.
111000
000111
101010
都是可以的
求组合数。jc()求阶乘。

import sys
from functools import reduce
from operator import mul
def jc(n):
    return reduce(mul, range(1, n+1), 1)
def f(n,m):
    print(int(jc(m+n)/jc(n)/jc(m)))
for line in sys.stdin:
    l=line.strip().split(' ')
    n,m=int(l[0]),int(l[1])
    f(n,m)