在上一篇中，我們通過分析，順利完成了“三角形最小路徑和”的動态規劃題解。在本節中，我們繼續看一道相似題型，以求能完全掌握這種“路徑和”的問題。話不多說，先看題目：
01、題目分析
| 第64題：最小路徑和 |
|---|
| 給定一個包含非負整數的 m x n 網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。 |
說明：每次隻能向下或者向右移動一步。
示例:
輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小。
複制
這道題有一定難度哦！如果沒有思路請回顧上一篇的學習内容！
不建議直接看題解！
02、題目圖解
首先我們分析題目，要找的是 最小路徑和， 這是個啥意思呢？假設我們有一個 m * n 的矩形 ：[[1,3,1],[1,5,1],[4,2,1]]
那從左上角到右下角的最小路徑和，我們可以很容易看出就是 1-3-1-1-1 ，這一條路徑，結果等于 7 。
題目明确了，我們繼續進行分析。該題與上一道求三角形最小路徑和一樣，題目明顯符合可以從子問題的最優解進行建構，是以我們考慮使用動态規劃進行求解。首先，我們定義狀态：
dp[i][j] : 表示包含第i行j列元素的最小路徑和
同樣，因為任何一條到達右下角的路徑，都會經過 [0,0] 這個元素。是以我們需要對 dp[0][0] 進行初始化。
dp[0][0] = [0][0]位置所在的元素值
繼續分析，根據題目給的條件，如果我們要求 dp[i][j] ，那麼它一定是從自己的上方或者左邊移動而來。如下圖所示：
5，隻能從3或者1移動而來2，隻能從5或者4移動而來4，從1移動而來3，從1移動而來 （紅色位置必須從藍色位置移動而來）
進而我們得到狀态轉移方程：
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
同樣我們需要考慮兩種特殊情況：
- 最上面一行，隻能由左邊移動而來（1-3-1）
- 最左邊一列，隻能由上面移動而來（1-1-4）
最後，因為我們的目标是從左上角走到右下角，整個網格的最小路徑和其實就是包含右下角元素的最小路徑和。即：
設：dp的長度為l 最終結果就是：dp[l-1][len(dp[l-1])-1]
綜上我們就分析完了，我們總共進行了 4 步：
- 定義狀态
- 總結狀态轉移方程
- 分析狀态轉移方程不能滿足的特殊情況。
- 得到最終解
03、GO語言示例
根據以上分析，可以得到代碼如下：
func minPathSum(grid [][]int) int {
l := len(grid)
if l < 1 {
return 0
}
dp := make([][]int, l)
for i, arr := range grid {
dp[i] = make([]int, len(arr))
}
dp[0][0] = grid[0][0]
for i := 0; i < l; i++ {
for j := 0; j < len(grid[i]); j++ {
if i == 0 && j != 0 {
dp[i][j] = dp[i][j-1] + grid[i][j]
} else if j == 0 && i != 0 {
dp[i][j] = dp[i-1][j] + grid[i][j]
} else if i !=0 && j != 0 {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
}
}
}
return dp[l-1][len(dp[l-1])-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
複制
運作結果：
同樣，運作上面的代碼，我們發現使用的記憶體過大。有沒有什麼辦法可以壓縮記憶體呢？通過觀察我們發現，在我們自左上角到右下角計算各個節點的最小路徑和的過程中，我們隻需要使用到之前已經累積計算完畢的資料，并且不會再次通路之前的元素資料。繪制成圖如下：(大家看這個過程像不像掃雷，其實如果大家研究掃雷外挂的話，就會發現在掃雷的核心算法中，就有一處頗為類似這種分析方法，這裡就不深究了)
優化後的代碼如下：
func minPathSum(grid [][]int) int {
l := len(grid)
if l < 1 {
return 0
}
for i := 0; i < l; i++ {
for j := 0; j < len(grid[i]); j++ {
if i == 0 && j != 0 {
grid[i][j] = grid[i][j-1] + grid[i][j]
} else if j == 0 && i != 0 {
grid[i][j] = grid[i-1][j] + grid[i][j]
} else if i !=0 && j != 0 {
grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
}
}
}
return grid[l-1][len(grid[l-1])-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
複制
運作結果：
java：
class Solution {
public int minPathSum(int[][] grid) {
int l = grid.length;
if (l < 1) {
return 0;
}
for(int i = 0; i < l; i++) {
for(int j = 0; j < grid[i].length; j++) {
if (i == 0 && j != 0) {
grid[i][j] = grid[i][j-1] + grid[i][j];
} else if (j == 0 && i != 0) {
grid[i][j] = grid[i-1][j] + grid[i][j];
} else if (i !=0) {
grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
}
}
}
return grid[l-1][grid[l-1].length - 1];
}
public int min(int a, int b) {
return a > b ? b : a;
}
}
複制
運作結果：
課後思考：路徑和類問題和之前的子序列類問題有何差別？
我們歡迎你！
我把我寫的所有題解、以及一百張思維導圖和一千本開源電子書都放在了公衆号中~下方掃碼回複【資源】即可擷取！同時可回複【招聘】加入 BAT 萬人求職群！
随意展示一張導圖内容（所有的子節點都可以打開）：
今日論點：
面試造航母，工作擰螺絲是真的嗎?
一些架構、專家、顧問崗，這種體會沒那麼強烈，但對于多數開發人員，每天幹的工作是增删改查，與面試時的各種問題想較，偏差很大。
由于it行業的高薪資，各種行業都往過來轉，公司出于應對異常情況的工作必要、壓價、篩選候選人等考慮會提高門檻，當然也不乏一些面試官為了炫技，某些不良公司為了套方案，這樣才造成了這種怪像。
大家怎麼看呢？評論區留下你的想法吧！