# Leetcode 62. Unique Paths

## 題解

### DFS (TLE)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Time complexity: O(m*n)
        # Space complexity: O(m*n)
        if m == 1 or n == 1:
            return 1
        return self.uniquePaths(m-1,n) + self.uniquePaths(m,n-1

### 動態規劃

#### 二維數組空間解


如上圖，先使用 dfs 窮舉，找出規律，得出二維數組的狀態轉移方程

paths[_m][_n] = paths[_m-1][_n] + paths[_m][_n-1]

為了處理邊界問題，在初始化二維數組的時候，把所有的數字都設為 1，並且遍歷的時候從 1 開始

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Time complexity: O(m-1*n-1)
        # Space complexity: O(m*n)
        paths = [[1 for i in range(n)] for i in range(m)]
        for _m in range(1,m):
            for _n in range(1,n):
                paths[_m][_n] = paths[_m-1][_n] + paths[_m][_n-1]
        return paths[m-1][n-1]

#### 狀態壓縮 (一維數組)

從上一個解中，可以看出一個規律，每一次做狀態轉移的時候，都只會用到 _m - 1 和 _n - 1 的資料，也就是說，dp 數組只需要紀錄 n 個大小即可 (如上圖)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Time complexity: O(m-1*n-1)
        # Space complexity: O(n)
        dp = [1 for i in range(n)]
        left = 1
        for _m in range(1,m):
            left = 1
            for _n in range(1,n):
                dp[_n] = left + dp[_n]
                left = dp[_n]
        return left

更優化 (發現左邊的狀態其實就是上一個狀態)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Time complexity: O(m-1*n-1)
        # Space complexity: O(n)
        dp = [1 for i in range(n)]
        for _m in range(1,m):
            for _n in range(1,n):
                dp[_n] = dp[_n-1] + dp[_n]
        return dp[-1]