64. 最小路径和
64. 最小路径和
题目
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
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
解题思路
动态规划:使用动态规划来解决问题。定义一个二维数组
dp
,其中dp[i][j]
表示从(0, 0)
到(i, j)
的最小路径和。状态转移方程:可以从左上角到达
(i, j)
的路径有两条:从(i-1, j)
向下移动和从(i, j-1)
向右移动。因此,状态转移方程为dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
。边界条件:对于第一行和第一列,由于它们只能从上方或左侧移动到达,所以路径和等于前一个格子的路径和加上当前格子的值。即
dp[0][j] = dp[0][j-1] + grid[0][j]
和dp[i][0] = dp[i-1][0] + grid[i][0]
。初始化:初始化第一行和第一列的路径和。
复杂度分析
- 时间复杂度:
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 | 摘樱桃 | 数组 动态规划 矩阵 | ||
1937 | 扣分后的最大得分 | 数组 动态规划 矩阵 | ||
2087 | 网格图中机器人回家的最小代价 | 贪心 数组 | ||
2304 | 网格中的最小路径代价 | 数组 动态规划 矩阵 | ||
2435 | 矩阵中和能被 K 整除的路径 | 数组 动态规划 矩阵 | ||
2510 | 检查是否有路径经过相同数量的 0 和 1 🔒 | 数组 动态规划 矩阵 | ||
2662 | 前往目标的最小代价 | 图 数组 最短路 1+ |