一文搞定 LeetCode 64. 最小路径和（多维动态规划版）

大家好这篇文章快速记录LeetCode 64 最小路径和的最优解法思路清晰、代码简短适合新手直接理解背诵。题目给定一个非负整数网格从左上角到右下角只能向右/向下走求路径和最小的值。核心思路动态规划 原地修改第一行只能从左边来 → 累加第一列只能从上面来 → 累加其他格子当前值 当前值 min(上边, 左边)完整代码JSvarminPathSumfunction(grid){constmgrid.length;// 行数constngrid[0].length;// 列数// 初始化第一行for(leti1;in;i){grid[0][i]grid[0][i-1];}// 初始化第一列for(leti1;im;i){grid[i][0]grid[i-1][0];}// 计算剩余格子for(leti1;im;i){for(letj1;jn;j){grid[i][j]Math.min(grid[i-1][j],grid[i][j-1]);}}returngrid[m-1][n-1];};代码逐行解释获取行列m行数n列数第一行处理只能从左侧过来直接累加第一列处理只能从上方过来直接累加通用公式每个格子取上方/左侧更小的值加上当前值返回结果右下角就是最小路径和复杂度时间O(m*n) 遍历一次网格空间O(1) 原地修改无额外空间