【題目】

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

說明： 每次只能向下或者向右移動一步。

示例 1：

image.png

輸入： grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出： 7
解釋： 因為路徑 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

【題目解析】

解題方法

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

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

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # 獲取網(wǎng)格的行數(shù)和列數(shù)
        m, n = len(grid), len(grid[0])
        
        # 動態(tài)規(guī)劃求解
        for i in range(m):
            for j in range(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é)】

適用問題類型

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

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

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

實踐意義

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

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

題目鏈接

最小路徑和