LeetCode 064 Minimum Path Sum

LeetCode

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 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

m == grid.length n == grid[i].length
1 <= m, n <= 200 0 <= grid[i][j] <= 100

题目大意：

求矩阵最短路径和。只能向下向右走。

解题思路：

递归式：

1	dp[i][j] = min{dp[i-1][j], dp[i][j-1]} + grid[i - 1][j - 1]

解题步骤：

N/A

注意事项：

初始值为最大值，dp[0][1] = dp[1][0] = 0确保左上格正确。
模板四点注意事项

Python代码：

# dp[i][j] = min{dp[i-1][j], dp[i][j-1]} + grid[i - 1][j - 1]
def minPathSum(self, grid: List[List[int]]) -> int:
	dp = [[float('inf') for _ in range(len(grid[0]) + 1)] for _ in range(len(grid) + 1)]
	dp[0][1] = dp[1][0] = 0
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
	return dp[-1][-1]

算法分析：

时间复杂度为O(n²)，空间复杂度O(n²)