LeetCode 064 Minimum Path Sum

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

<pre>Input: grid = [[1,2,3],[4,5,6]] Output: 12 </pre>

Constraints:

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

</div>

题目大意：

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

解题思路：

递归式：

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

解题步骤：

N/A

注意事项：

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

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]

算法分析：

时间复杂度为<code>O(n²)</code>，空间复杂度<code>O(n²)</code>