Minimum Path Sum

題意：

　　給定一個方格，每個格子中有一個數字，現在我們要找一條從方格左上角出發直到方格右下角的路，條件是這條路經過的數字之和為最小。

解題思路：

　　此題仍然是動態規劃類型的問題，關鍵是我們如何將這個問題劃分為多個類似階段。

　　目前的想法是可不可以先找到小方格內的最小路徑，然后在去利用當前的結果去找比他大的方格的最小路徑。如果是這樣的話，大方格的最小路徑一定會路過小方格最小路徑嗎？（一定會到達小方格的左上角嗎？）這一點還不能確定。

　　從剛才的想法我衍生出來另一種方法，首先我們觀察我們每一步影響到的方塊數，我們會發現隨著路徑長度的增加，我們是以階梯形狀向上推進的（假設我們從右下方往左上方找）。像這樣：

ＯＯＯ　　?。希希稀　　。希希亍　　。希兀亍　　。兀兀?/span>

ＯＯＯ　＞?。希希亍。尽。希兀亍。尽。兀兀亍。尽。兀兀?/span>

ＯＯＸ　　　ＯＸＸ　　?。兀兀亍　　。兀兀亍　　。兀兀?/span>

　　依照動態規劃的思想，在每個階段，我們可以將打叉的區域的方格數字標記為從右下角出發到達當前方格的最短路徑長度。層層遞增，那么有當前　

matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1])

　　假設我們有一個矩陣如下：

Ｓ５０

１６０

４３Ｅ

　　那么首先我們先更新矩陣右下角兩條邊的最短路徑，然后在依次往上更新矩陣：

Ｓ５０　　　Ｓ５０　　?。?span style="color: #ff0000;">５０　　　（Ｓ＋５）５０

１６０?。尽。?span style="color: #ff0000;">９０?。尽?span style="color: #ff0000;">８９０　＞　　　８　?。梗?/span>

７３Ｅ　　　７３Ｅ　　　７３Ｅ　　　　　７　　３Ｅ

　　于是程序我們就可寫成：

class Solution:    # @param {integer[][]} grid    # @return {integer}    def minPathSum(self, grid):        m = len(grid)        n = len(grid[0])        for i in range(1,m):            grid[i][0] += grid[i-1][0]        for j in range(1,n):            grid[0][j] += grid[0][j-1]        for i in range(1,m):            for j in range(1,n):                grid[i][j] += min(grid[i-1][j], grid[i][j-1])        return grid[-1][-1]