pydata

Keep Looking, Don't Settle

leetcode 64. Minimum Path Sum

题目大意:从一个\(m \times n\)的格子左上角走到右下角,每个格子有一个非负整数,只能向右或者向下走,要找到一条路径使得格子里的数字的和最小?

这道题和62 63都比较相似,只是格子里面加了数字。跟骑士跟公主的那道题也相似。

62. Unique Paths

63. Unique Paths II

64. Minimum Path Sum

174. Dungeon Game

741. Cherry Pickup

1. 采用记忆化递归

class Solution(object):
    def minPathSum(self, grid):
        self.grid = grid
        m = len(grid)
        n = len(grid[0])
        self.f = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        self.f[1][1] = grid[0][0]
        def dp(y, x):
            if x < 1 or y < 1:
                return float('inf')
            if y == 1 and x == 1:
                return self.grid[0][0]
            if self.f[y][x] > 0:
                return self.f[y][x]
            else:
                self.f[y][x] = min(dp(y - 1, x), dp(y, x - 1)) + self.grid[y - 1][x - 1]
                return self.f[y][x]
        return dp(m, n)

2. 使用递推(动态规划)的办法,类似62题和63题:

class Solution(object):
    def minPathSum(self, grid):
        self.grid = grid
        m = len(grid)
        n = len(grid[0])
        self.f = [[float('inf') for _ in range(n + 1)] for _ in range(m + 1)]
        self.f[1][1] = grid[0][0]
        def dp(y, x):
            for y in range(1, m + 1):
                for x in range(1, n + 1):
                    if y == 1 and x == 1:
                        continue
                    else:
                        self.f[y][x] = min(self.f[y - 1][x], self.f[y][x - 1]) + self.grid[y - 1][x - 1]
        dp(m + 1, n + 1)
        return self.f[m][n]

3. 使用递推,直接修改原矩阵

直接修改原来的矩阵grid,这样不会有额外的空间开销

class Solution(object):
    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        for y in range(m):
            for x in range(n):
                if y == 0 and x == 0:
                    continue
                elif y == 0:
                    grid[y][x] += grid[y][x - 1]
                elif x == 0:
                    grid[y][x] += grid[y - 1][x]
                else:
                    grid[y][x] += min(grid[y][x - 1], grid[y - 1][x])
        return grid[m - 1][n - 1]