最小路径和-动态规划

孙泽辉

发布于：2021年7月17日

字数：206字

时长：1分钟

次浏览

很经典的动态规划题

递推公式：MIN（左边+当前，上边+当前）

边界：最左列和最上行

// 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
// 输出：7
// 解释：因为路径 1→3→1→1→1 的总和最小。
function solution(grid: number[][]) {
    let row: number = grid.length, col: number = grid[0].length;
    let dp: number[][] = new Array(row).fill(0).map(arr => (new Array(col).fill(0)))
    dp[0][0] = 1
    dp[-1] = new Array(col).fill(Infinity)

    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            dp[i][-1] = Infinity;
            if (i === 0 && j === 0) continue;
            dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
        }
    }
    return dp[row - 1][col - 1]
}


const r = solution([[1, 3, 1], [1, 5, 1], [4, 2, 1]])
console.log(r) // 7

64. 最小路径和 - 力扣（LeetCode） (leetcode-cn.com)

leetcode 64. 最小路径和 #动态规划_哔哩哔哩_bilibili