题解 | #不同路径的数目(一)#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        # 根据题目可以知道，每个格子只能从它的上面一格或左面一格到达
        # 那么到达每一格的不同路径就可以等于到达上面一格的路径加上到达左面一格的路径
        dp = [[0] * n for _ in range(m)]
        dp[0] = [1] * n

        for i in range(m):
            dp[i][0] = 1

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[m-1][n-1]