题解 | #求路径#

'''
解题思路：
矩阵路径数
dp[i][j]表示前i行、j列的路径数，状态公式如下：
如果i >= 2 && j >= 2，那么dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[1][k] = 1
dp[k][1] = 1
解释如下：
当列数和行数大于2的时候，当前节点的路径数为左侧节点路径数+右侧节点路径数
当列数或行数为1时，当前节点的路径数恒为1
#=============================================================================================
'''
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m , n ):
        # write code here
        dp = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if (i==0 or j==0):
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[-1][-1]