LeetCode-62-不同路径

image.png
image.png

解题思路：

1. dp[i][j]表示走到第i-1行、第j-1列时包含的可能路径；
2. 当前点dp[i][j]的可能来源状态由上方dp[i-1][j]或左方dp[i][j-1]来，那么可能的路径即两个状态之和，dp[i][j] = dp[i-1][j] + dp[i][j-1]。
3. 边界初始化，第一行和第一列的路径数为1。

Python3代码：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(n):
            dp[0][i] = 1
        for j in range(m):
            dp[j][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[-1][-1]