最小路径和

yingl · yingl · commit 7fd8b4a5b605 · 2016-07-30T01:32:57.000+08:00
diff --git a/minimum_path_sum.py b/minimum_path_sum.py
@@ -0,0 +1,25 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    """
+    @param grid: a list of lists of integers.
+    @return: An integer, minimizes the sum of all numbers along its path
+    """
+    def minPathSum(self, grid):
+        # write your code here
+        rows, cols = len(grid), len(grid[0])
+        self.min_paths = [[-1] * cols for row in xrange(rows)]
+        self.min_paths[0][0] = grid[0][0]
+        return self.dfs(grid, rows - 1, cols - 1)
+        
+    def dfs(self, grid, row, col):
+        if self.min_paths[row][col] >= 0:
+            return self.min_paths[row][col]
+        if (row >= 1) and (col >= 1):
+            dist = grid[row][col] + min(self.dfs(grid, row - 1, col), self.dfs(grid, row, col - 1))
+        elif row >= 1:
+            dist = grid[row][col] + self.dfs(grid, row - 1, col)
+        elif col >= 1:
+            dist = grid[row][col] + self.dfs(grid, row, col - 1)
+        self.min_paths[row][col] = dist
+        return dist
