題目出處

62. Unique Paths

難度

Medium

個人範例程式碼

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if not m or not n:
            return 0

        dp = [[1 for _ in range(n)] for _ in range(m)]

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

        return dp[-1][-1]

算法說明

也是經典的二維 DP 問題，
透過建立下方的圖片，就可以求得所有路徑的答案

(DP 記錄到達那一格的所有方法數)

input handling

如果沒有 m 或 n，return 0 (無方法)

Boundary conditions

用 for 來控制 DP 的範圍

Reference