题解 | #走方格的方案数#
走方格的方案数
https://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b
给出Python3版本代码：
方法一：递归
def f(n, m):
if n == 0 or m == 0:
return 1
else:
return f(n - 1, m) + f(n, m - 1)
while True:
try:
n, m = map(int, input().split())
print(f(n, m))
except:
break
方法二：动态规划
while True:
try:
n, m = map(int, input().split())
dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(0, n + 1):
for j in range(0, m + 1):
if i == 0 and j == 0:
dp[i][j] = 1
elif i == 0:
dp[i][j] = dp[i][j - 1]
elif j == 0:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[n][m])
except:
break
方法三：数学排列组合
while True: try: n, m = map(int, input().split()) a, b= 1, 1 for i in range(1, n + 1): a *= m + i # 分子 b *= i # 分母 print(a // b) except: break
