【題目】

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

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

示例 1：

image.png

輸入： grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出： 7
解釋： 因?yàn)槁窂?1→3→1→1→1 的總和最小。

示例 2：

輸入： grid = [[1,2,3],[4,5,6]]
輸出： 12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

【題目解析】

解題方法

這個(gè)問題可以通過動(dòng)態(tài)規(guī)劃（Dynamic Programming, DP）來解決。動(dòng)態(tài)規(guī)劃是一種將復(fù)雜問題分解成小問題解決的方法，通過解決子問題，逐步推導(dǎo)出整個(gè)問題的最優(yōu)解。

對(duì)于這個(gè)問題，我們可以創(chuàng)建一個(gè)同樣大小的DP數(shù)組來存儲(chǔ)到達(dá)每個(gè)格子的最小路徑和。對(duì)于網(wǎng)格中的每一個(gè)格子，只能從上面或者左邊移動(dòng)過來，因此到達(dá)該格子的最小路徑和就是它上面的格子和左邊格子的最小路徑和中較小的那一個(gè)加上當(dāng)前格子的值。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # 獲取網(wǎng)格的行數(shù)和列數(shù)
        m, n = len(grid), len(grid[0])
        
        # 動(dòng)態(tài)規(guī)劃求解
        for i in range(m):
            for j in range(n):
                # 如果不是起點(diǎn)
                if i != 0 or j != 0:
                    # 如果在網(wǎng)格的最左邊，則只能從上面來
                    if j == 0:
                        grid[i][j] += grid[i-1][j]
                    # 如果在網(wǎng)格的最上邊，則只能從左邊來
                    elif i == 0:
                        grid[i][j] += grid[i][j-1]
                    # 否則，選擇從上面來和從左邊來的較小者
                    else:
                        grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        # 返回到達(dá)網(wǎng)格右下角的最小路徑和
        return grid[m-1][n-1]

執(zhí)行效率

image.png

【總結(jié)】

適用問題類型

動(dòng)態(tài)規(guī)劃算法特別適用于那些問題，其中最優(yōu)解可以通過決策序列的方式來得到，且每個(gè)決策依賴于前一個(gè)狀態(tài)的結(jié)果。這類問題通常具有重疊子問題和最優(yōu)子結(jié)構(gòu)的特點(diǎn)，使得DP算法能夠有效減少計(jì)算重復(fù)，通過局部最優(yōu)解推導(dǎo)出全局最優(yōu)解。“最小路徑和”問題是一個(gè)典型的最優(yōu)路徑問題，要求找到從網(wǎng)格左上角到右下角的最小總和路徑，完全符合動(dòng)態(tài)規(guī)劃適用的問題類型。

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

• 算法特點(diǎn)：動(dòng)態(tài)規(guī)劃的核心在于解決重疊子問題并利用這些子問題的解來構(gòu)建最終解。該方法通過構(gòu)建一個(gè)DP表（通常是二維數(shù)組），其中DP表的每個(gè)元素代表到達(dá)該位置的最小路徑和，從而避免了重復(fù)計(jì)算，并確保了算法的高效性。
• 時(shí)間復(fù)雜度與空間復(fù)雜度：對(duì)于“最小路徑和”問題，動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為O(mn)，其中m是網(wǎng)格的行數(shù)，n是網(wǎng)格的列數(shù)，因?yàn)樾枰闅v整個(gè)網(wǎng)格來填充DP表。空間復(fù)雜度也是O(mn)，因?yàn)樾枰粋€(gè)同樣大小的DP表來存儲(chǔ)每個(gè)位置的最小路徑和。在一些情況下，如果能夠原地修改輸入網(wǎng)格或者使用滾動(dòng)數(shù)組技巧，空間復(fù)雜度可以優(yōu)化到O(n)或更低。

實(shí)踐意義

動(dòng)態(tài)規(guī)劃不僅適用于“最小路徑和”這一特定類型的問題，它在算法設(shè)計(jì)和問題解決中占據(jù)著重要地位，能夠解決包括但不限于路徑問題、序列問題、背包問題等多種類型的問題。掌握動(dòng)態(tài)規(guī)劃算法，對(duì)于提高解決復(fù)雜問題的能力、優(yōu)化程序性能具有重要意義。在軟件開發(fā)和數(shù)據(jù)分析領(lǐng)域，動(dòng)態(tài)規(guī)劃算法的應(yīng)用范圍廣泛，從提升算法效率到優(yōu)化資源分配等方面都發(fā)揮著關(guān)鍵作用。

綜上所述，通過應(yīng)用動(dòng)態(tài)規(guī)劃算法解決“最小路徑和”問題，不僅能夠有效提升問題解決的效率和質(zhì)量，還能夠深化對(duì)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)原理和應(yīng)用場景的理解。

題目鏈接

最小路徑和