Repository navigation
64. 最小路径和 #51
Description
状态定义
dp[i][j] 代表从 (0, 0) 走到 (i, j) 的最小路径和。
状态转移方程
明确题意：只能向右或者向下走，也就是说终点 (i, j) 只能从 (i - 1, j) 或者 (i, j - 1) 走过来。
分为以下三种情况分别处理：
- 左边或者上边都是边界时，终点也就是起点。
dp[i][j] = grid[i][j]
- 左边或者上边为边界时：
grid[i][j] = grid[i - 1][j] + grid[i][j]grid[i][j] = grid[i][j - 1] + grid[i][j]
- 左边和上边都不为边界时：
grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
const minPathSum = function(grid) {
const n = grid.length
const m = grid[0].length
const dp = Array.from(new Array(n), () => new Array(m))
for (let i = 0; i < n ; i++) {
for (let j = 0; j < m; j++) {
if (i !== 0 && j !== 0) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
} else if (i !== 0 && j === 0) {
dp[i][j] = dp[i - 1][j] + grid[i][j]
} else if (i === 0 && j !== 0) {
dp[i][j] = dp[i][j - 1] + grid[i][j]
} else if (i === 0 && j === 0) {
dp[i][j] = grid[i][j]
}
}
}
return dp[n - 1][m - 1]
}- 时间复杂度: O(m * n)
- 空间复杂度: O(m * n)
降维
不需要额外建立空间，直接遍历修改 grid[i][j]。
const minPathSum = function(grid) {
const n = grid.length
const m = grid[0].length
for (let i = 0; i < n ; i++) {
for (let j = 0; j < m; j++) {
if (i !== 0 && j !== 0) {
grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
} else if (i !== 0 && j === 0) {
grid[i][j] = grid[i - 1][j] + grid[i][j]
} else if (i === 0 && j !== 0) {
grid[i][j] = grid[i][j - 1] + grid[i][j]
} else if (i === 0 && j === 0) {
grid[i][j] = grid[i][j]
}
}
}
return grid[n - 1][m - 1]
}- 时间复杂度: O(m * n)
- 空间复杂度: O(1)
Activity