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

# !/usr/bin/env python3
# -*- coding: utf-8 -*-
__author__ = 'tianyi'
__date__ = '2024/3/24 09:15 '
__file__ = 'HW_HJ91.py'

import sys
String1 = sys.stdin.readline().rstrip()
List1 = String1.split()
#动态规划走方格，输出走到右下角的路径数
#输入：m n
#输出：路径数
def dp(n, m):
    dp = [[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n+1):
        for j in range(m+1):
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[n][m]
print(dp(int(List1[0]), int(List1[1])))

#解释代码 ： 用dp[i][j]表示走到(i,j)的路径数，dp[i][j] = dp[i-1][j] + dp[i][j-1]，即走到(i,j)的路径数等于走到(i-1,j)的路径数加上走到(i,j-1)的路径数。 # dp[0][j] = dp[i][0] = 1，即第一行和第一列的路径数都是1。 最后返回dp[n][m]即可。    时间复杂度O(n*m)，空间复杂度O(n*m)。