64.最小経路和(Python)

タイトル
難易度:★☆☆タイプ:数学方法:ダイナミックプランニング
トランスファゲート
非負の整数を含むmxnメッシュを指定します.左上から右下に向かうパスを見つけて、パスの数値の合計が最小になります.
説明:毎回1歩下または右に移動するしかありません.
例
入力:[[1,3,1],[1,5,1],[4,2,1]]出力:7解釈:パス1→3→1→1→1の総和が最小であるため.
に答える
前の問題と似ていて、典型的な動的計画問題です.
各位置の要素dp[i][j]が位置(i,j)に到達したときの最小経路和を表すマトリクスdpを設定する.
しょきじょうたい
i=0、第1行、このときdp[0][j]は、第1行位置j以前のすべての要素の和を表す.j=0、第1列、このときdp[i][0]は、第1列位置i以前のすべての要素の和を表す.
じょうたいてんいほうていしき
非第1行および第1列要素の場合、状態遷移方程式が存在します.
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + dp[i, j]
最終状況
dpマトリクスの右下隅の要素を選択して結果として返せばよい.

class Solution:
    def minPathSum(self, grid):
        m, n = len(grid), len(grid[0])

        #      
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]

        #      
        for j in range(1, n):
            grid[0][j] += grid[0][j-1]

        #       
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])

        #       
        return grid[-1][-1]


if __name__ == "__main__":
    s = Solution()
    print(s.minPathSum([
        [1, 3, 1, 2],
        [1, 5, 1, 1],
        [4, 2, 1, 1]
    ]))

質問やアドバイスがあれば、コメントエリアへようこそ~