---
# System prepended metadata

title: 64. Minimum Path Sum
tags: [Leetcode, Python]

---

# 64. Minimum Path Sum
###### tags: `Python`,`Leetcode`
https://leetcode.com/problems/minimum-path-sum/description/

## MyCode!
![](https://i.imgur.com/jFbYqzU.png)

## 解題思路
* 題目要求要找到由左上角至右下角最小總和之路徑
* 將每個 Grid 值改為**所經的最小總和**
  1. 這樣做的好處就是最後 Output 就是右下角（座標 [-1][-1] 的值）
* 從最上列、最左行的總和開始算起（因為邊邊的格子只有一條路可以到達，口憐）
* 接下來在列與行之間的 Grid 也要從左邊/最上面的值找出最小的值相加，這樣該 Grid 也會被更新為**所經最小總和**

## 步驟
![](https://i.imgur.com/OiNAjLH.png)
▲ 原題目給的 Grid

### Step 1：得知 Grid 的長與寬
### Step 2：第一個 for 迴圈更新第一行每一格的最小路徑和
![](https://i.imgur.com/itTtyzi.png)
▲ 原題目第一行數值狀態
![](https://i.imgur.com/nWBRUML.png)
▲ 原題目第一行數值更新後狀態

### Step 3：第二個 for 迴圈更新第一列每一格的最小路徑和
![](https://i.imgur.com/YzZXQxe.png)
▲ 原題目第一列數值狀態
![](https://i.imgur.com/27FrjIT.png)
▲ 原題目第一行數值更新後狀態

### Step 4：第三個雙 for 迴圈找出中間的每一個最小路徑和
![](https://i.imgur.com/KLwPuwh.png)

### Step 5：Return 坐下角該格（因為那一格就是最小路徑和）