LeetCode 64. Minimum Path Sum.jpg
LeetCode 64. Minimum Path Sum
Description
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
描述
给定m x n网格填充非负数，找到从左上到右下的路径，这最小化了沿其路径的所有数字的总和。
注意：您只能在任何时间点向下或向右移动。
思路
- 这道题是给定一个m * n的矩阵，让从左上角走到右下角，每一个位置都有一个权重，让返回一条路径上所有权重和，要求是此和最小.
- 这道题同第62题，第63题思路非常类似，第62题解析在这里，第63题在这里.
- 我们假设有矩阵Matrix[m][n],矩阵Matrix[i][j]位置只能由Matrix[i-1][j]和Matrix[i][j-1]到达.
- 因此，到达Matrix[i][j]的最短路径 = Min {Matrix[i-1][j],Matrix[i][j-1]} + Matrix[i][j]
- 即到达矩阵当前位置的最小权重路径 = {到达矩阵当前位置左边的最小权重路径，到达矩阵当前位置上边的最小权重路径}中的最小值 + 矩阵当前位置的权重
class Solution:
# 递归版本，当前位置最小值 = min{当前位置左边最小值，当前位置上边最小值}+当前位置的值
def __init__(self):
# 声明结果矩阵，用于记录已经遍历过的位置
self.res = []
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# 入股gird为空，则直接返回
if not grid:
return 0
# 获取最大行的索引，获取最大列的索引
row, col = len(grid)-1, len(grid[0])-1
# 初始化第一行，每一个位置的最短路径 = 左边的最短路径+本身的值
for i in range(1, col+1):
grid[0][i] += grid[0][i-1]
# 初始化第一列，每一个位置的最短路径 = 上边的最短路径+本身的值
for i in range(1, row+1):
grid[i][0] += grid[i-1][0]
# 初始化结果矩阵，-1表示当前位置还没有遍历过
self.res = [[-1 for _ in range(col+1)] for _ in range(row+1)]
return self.recur(row, col, grid)
def recur(self, row, col, grid):
# 如果到达矩阵左上角的位置，返回此位置的路径值
if row == 0 and col == 0:
return grid[0][0]
# 如果到达第一行但不是最坐上角
elif row == 0:
return grid[0][col]
# 如果到达第一列但不是最左上角
elif col == 0:
return grid[row][0]
# 如果当前位置已经遍历过
elif self.res[row][col] != -1:
return self.res[row][col]
# 求矩阵当前位置做左边的最小值
left = self.recur(row, col-1, grid)
# 求矩阵当前位置上边的最小值
top = self.recur(row-1, col, grid)
# 记录矩阵当前位置的值
self.res[row][col] = min(left, top)+grid[row][col]
# 返回矩阵当前位置的值
return self.res[row][col]
class Solution2:
# 循环版本实现，当前位置最小值 = min{当前位置左边最小值，当前位置上边最小值}+当前位置的值
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# 如果gird矩阵为空，则直接返回
if not grid:
return 0
# 获得行的最大索引，获得列的最大索引
row, col = len(grid)-1, len(grid[0])-1
# 初始化第一行，当前位置最短路径 = 当前位置左边最短路径 + 当前位置的值
for i in range(1, col+1):
grid[0][i] += grid[0][i-1]
# 初始化第一列，当前位置最短路径 = 当前位置上边最短路径 + 当前位置的值
for i in range(1, row+1):
grid[i][0] += grid[i-1][0]
# 遍历每一个位置，当前位置最短路径 = min {当前位置左边最短路径，当前位置上边最短路径} + 当前位置的值
for i in range(1, row+1):
for j in range(1, col+1):
grid[i][j] = min(grid[i-1][j], grid[i][j-1])+grid[i][j]
return grid[row][col]
