# Leetcode 64. Minimum Path Sum

## 題解

### 動態規劃

#### In place 替換

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # DP
        # Time complexity: O(m*n)
        # Space complexity: O(m*n)
        m,n = len(grid),len(grid[0])
        for i in range(1,m*n): # 從 1 開始 避免邊界問題
            y,x = i // n, i % n
            if y == 0:
                grid[y][x] += grid[y][x-1]
            elif x == 0:
                grid[y][x] += grid[y-1][x]
            else:
                grid[y][x] += min(grid[y][x-1],grid[y-1][x])
        return grid[m-1][n-1]