最小路徑和

題目描述：給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說(shuō)明：每次只能向下或者向右移動(dòng)一步。

示例說(shuō)明請(qǐng)見(jiàn)LeetCode官網(wǎng)。

來(lái)源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/minimum-path-sum/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：窮舉法 遞歸

遞歸方法minPathSum的參數(shù)為當(dāng)前的坐標(biāo)和當(dāng)前的路徑和，遞歸過(guò)程如下：

• 如果當(dāng)前坐標(biāo)已經(jīng)是走到右下角了，判斷當(dāng)前的路徑和是否比已有的最小值小，如果是，則更新最小值；

• 如果當(dāng)前坐標(biāo)走到最右邊了，則坐標(biāo)往下移，遞歸處理；

• 如果當(dāng)前坐標(biāo)走到最下邊了，則坐標(biāo)往右移，遞歸處理；

• 如果當(dāng)前坐標(biāo)不在邊上，則需要遞歸2次分別往下移和往右移。

最后，返回最小值。

解法二：動(dòng)態(tài)規(guī)劃

• 首先，聲明一個(gè)和grid同樣大小的二維數(shù)組dp用來(lái)存儲(chǔ)到達(dá)相應(yīng)單元格的累加值；

• 初始化第一列的值；

• 初始化第一行的值；

• 然后遍歷后面的單元格，取左邊和上邊較小的值賦值；

• 最后返回dp[rows - 1][columns - 1]即為最小的和。

【每日寄語(yǔ)】 窮人缺什么：表面缺資金，本質(zhì)缺野心，腦子缺觀念，機(jī)會(huì)缺了解，骨子缺勇氣，改變?nèi)毙袆?dòng)，事業(yè)缺毅力。