Update 064.最小路径和.py

linwt · web-flow · commit 2b3a80b91c6a · 2019-06-07T17:06:43.000+08:00
diff --git a/leetcode/064.最小路径和.py b/leetcode/064.最小路径和.py
@@ -30,4 +30,23 @@ def minPathSum(self, grid):
                     grid[i][j] += grid[i-1][j]
                 else:
                     grid[i][j] += min(grid[i-1][j], grid[i][j-1])
-        return grid[-1][-1]
+        return grid[-1][-1]
+
+    
+# 动态规划经典写法
+class Solution(object):
+    def minPathSum(self, grid):
+        m, n = len(grid), len(grid[0])
+        dp = [[0]*n for _ in range(m)]
+        dp[0][0] = grid[0][0]
+        # 初始化首行首列
+        for i in range(1, m):
+            dp[i][0] = dp[i-1][0] + grid[i][0]
+        for j in range(1, n):
+            dp[0][j] = dp[0][j-1] + grid[0][j]
+        # 遍历每个位置
+        for i in range(1, m):
+            for j in range(1, n):
+                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
+                
+        return dp[-1][-1]
