64. 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] <= 200

题目大意

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

解题思路

1. 动态规划：使用动态规划来解决问题。定义一个二维数组 dp，其中 dp[i][j] 表示从 (0, 0) 到 (i, j) 的最小路径和。

2. 状态转移方程：可以从左上角到达 (i, j) 的路径有两条：从 (i-1, j) 向下移动和从 (i, j-1) 向右移动。因此，状态转移方程为 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。

3. 边界条件：对于第一行和第一列，由于它们只能从上方或左侧移动到达，所以路径和等于前一个格子的路径和加上当前格子的值。即 dp[0][j] = dp[0][j-1] + grid[0][j] 和 dp[i][0] = dp[i-1][0] + grid[i][0]。

4. 初始化：初始化第一行和第一列的路径和。

• 时间复杂度: O(m * n) - 遍历整个二维数组。
• 空间复杂度: O(1) - 由于dp[i][j] 只与 dp[i-1][j] 及 dp[i][j-1] 有关，所以可以直接原地修改 grid 数组。

代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
	const m = grid.length;
	const n = grid[0].length;
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (i == 0 && j == 0) {
				// 处理左上角的边界情况
				continue;
			} else if (i == 0) {
				// 处理第一行的边界情况
				grid[i][j] = grid[i][j - 1] + grid[i][j];
			} else if (j == 0) {
				// 处理第一列的边界情况
				grid[i][j] = grid[i - 1][j] + grid[i][j];
			} else {
				grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
			}
		}
	}
	return grid[m - 1][n - 1];
};

相关题目

相关题目

• 62. 不同路径
• 174. 地下城游戏
• 741. 摘樱桃
• 2304. 网格中的最小路径代价
• 1937. 扣分后的最大得分
• 2087. 网格图中机器人回家的最小代价
• 2435. 矩阵中和能被 K 整除的路径
• 🔒 Check if There is a Path With Equal Number of 0's And 1's
• 2662. 前往目标的最小代价

- [62. 不同路径](./0062.md)
- [174. 地下城游戏](./0174.md)
- [741. 摘樱桃](https://leetcode.com/problems/cherry-pickup)
- [2304. 网格中的最小路径代价](https://leetcode.com/problems/minimum-path-cost-in-a-grid)
- [1937. 扣分后的最大得分](https://leetcode.com/problems/maximum-number-of-points-with-cost)
- [2087. 网格图中机器人回家的最小代价](https://leetcode.com/problems/minimum-cost-homecoming-of-a-robot-in-a-grid)
- [2435. 矩阵中和能被 K 整除的路径](https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k)
- [🔒 Check if There is a Path With Equal Number of 0's And 1's](https://leetcode.com/problems/check-if-there-is-a-path-with-equal-number-of-0s-and-1s)
- [2662. 前往目标的最小代价](https://leetcode.com/problems/minimum-cost-of-a-path-with-special-roads)