leetcode 62. 不同路径

发表于 更新于 分类于 阅读次数：

解题思路

定义状态：
dp[i][j] := 从 (0, 0) 走到 (i, j) 不同的路径数目

动态规划转移方程：
dp[i][j] = dp[i][j-1] + dp[i-1][j]

状态压缩：
dp[j] += dp[j-1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [0 for i in range(n)]
        dp[0] = 1

        for row in range(m):
            for col in range(n):
                if col == 0:
                    continue
                dp[col] += dp[col-1]
        
        return dp[n-1]