算法筆試模拟題精解之“矩陣最小路徑和”

線上程式設計産品介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。

點選連結開始體驗：

https://developer.aliyun.com/coding

題目描述

難度：簡單

知識點：數組、DP

檢視題目：34.矩陣最小路徑和

給定一個矩陣，大小為m，從左上角開始每次隻能向右走或者向下走，最後達到右下角的位置。路徑中所有數字累加起來就是路徑和，傳回所有路徑的最小路徑和。

示例1

比如輸入矩陣為

4 1 5 3

3 2 7 7

6 5 2 8

8 9 4 5

最小路徑為

23

解題思路：動态規劃

本題可以用動态規劃的方法來解決。

計算一個格子到右下角的最小路徑需要兩個資料，一個是右邊格子到右下角的最小路徑，一個是下邊格子到右下角的最小路徑，兩個資料的較小值加上目前格子的數值即為最小路徑。

即 dp[i, j] = min(dp[i + 1, j], dp[i, j + 1]) + m[i, j]

由于計算目前格子最小路徑需要右邊和下邊格子的最小路徑。是以，需要從底向上進行決策。

本題用動态規劃法的難點之一是從底向上進行決策的順序。

如下圖所示，通過觀察可以發現，同一對角線上的數字的橫縱坐标和是相等的，我們以對角線的方向為順序，從右下角向左上角計算出每個格子的最小路徑。最後可計算得出 dp[0, 0]。

是不是有思路了呢，點選連結立刻答題：

34.矩陣最小路徑和