43 lines
976 B
JavaScript
43 lines
976 B
JavaScript
/*
|
||
* @lc app=leetcode id=64 lang=javascript
|
||
*
|
||
* [64] Minimum Path Sum
|
||
*/
|
||
/**
|
||
* @param {number[][]} grid
|
||
* @return {number}
|
||
*/
|
||
var minPathSum = function(grid) {
|
||
// 时间复杂度和空间复杂度都是 O (m * n);
|
||
if (grid.length === 0) return 0;
|
||
const dp = [];
|
||
const rows = grid.length;
|
||
const cols = grid[0].length;
|
||
// 实际上你也可以无差别全部填充为MAX_VALUE，对结果没影响,代码还会更少
|
||
// 只是有点不专业而已
|
||
for (let i = 0; i < rows + 1; i++) {
|
||
dp[i] = [];
|
||
// 初始化第一列
|
||
dp[i][0] = Number.MAX_VALUE;
|
||
for (let j = 0; j < cols + 1; j++) {
|
||
// 初始化第一行
|
||
if (i === 0) {
|
||
dp[i][j] = Number.MAX_VALUE;
|
||
}
|
||
}
|
||
}
|
||
|
||
// tricky
|
||
dp[0][1] = 0;
|
||
|
||
for (let i = 1; i < rows + 1; i++) {
|
||
for (let j = 1; j < cols + 1; j++) {
|
||
// state transition
|
||
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
|
||
}
|
||
}
|
||
|
||
return dp[rows][cols];
|
||
};
|
||
|