Leetcode題解 Python：四月挑戰DAY18 Minimum Path Sum

給一串二維數列(格線)，每個元素為非零整數，路徑只能往右或往下，找出從左上角到右下角的最短距離。

一看到往右或往下的二種可能性，DP就蠢蠢欲動，而且同個位置上的最短距離是固定的，完全可以使用DP去解。

dfs遞迴函數保存兩個訊息 y, x 記錄回傳值。自身加往下或住右較小的，即當前位置的最小距離。

如果到達邊界，由於 min() 不能比較 int 與 None ， 因此得針對邊界的下個距離做處理，這裡使用 [] 把下個距離放入串列再做比較。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        
        from functools import lru_cache
        @lru_cache(None)
        def dfs(y,x):
            if y == rows or x == cols:return []                
            d2 = dfs(y+1, x) + dfs(y, x+1)
            distance = grid[y][x] + (min(d2) if d2 else 0)
            return [distance]
        
        return dfs(0,0)[0]

又或者迴圈所有位置，每個位置加上左方與上方的最小值，等到迴圈結束，此時右下角為最短距離。