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

#两种方法：
#输入
list1=[int(x) for x in input().split()]
n,m=list1[0],list1[1]

#第一种：动态规划
# 初始化dp数组
dp = [[0] * (n + 1) for _ in range(m + 1)]
#注意不要使用dp=[[0]*(n+1)]*(m+1)，会导致每个子序列不独立

# 设置边界
dp[0][0]=1
for x in range(1,n+1):
    dp[0][x]=1
for y in range(1,m+1):
    dp[y][0]=1

for x in range(1, n + 1):
    for y in range(1, m + 1):
        dp[y][x] = dp[y - 1][x] + dp[y][x- 1]

print(dp[m][n])

#第二种方法：递归
def f(x,y):
    if x < 0 or y < 0:
        return 0
    elif x == 0 or y == 0:
        return 1
    else:
        return f(x-1,y)+f(x,y-1)
print(f(m,n)