leetcode64：最小路径和 #139

Activity

1. sisterAn

   added

   网易

   阿里

   on Dec 15, 2020
2. sisterAn commented on Jan 5, 2021

   

   sisterAn

   on Jan 5, 2021

   OwnerAuthor

   More actions

   1、DP方程
   当前项最小路径和 = 当前项值 + 上项或左项中的最小值
   grid[i][j] += Math.min( grid[i - 1][j], grid[i][j - 1] )

   2、边界处理
   grid的第一行与第一列 分别没有上项与左项 故单独处理计算起项最小路径和
   计算第一行：

   for(let j = 1; j < col; j++) grid[0][j] += grid[0][j - 1]

   计算第一列：

   for(let i = 1; i < row; i++) grid[i][0] += grid[i - 1][0]

   3、代码实现

   var minPathSum = function(grid) {
       let row = grid.length, col = grid[0].length
   
       // calc boundary
       for(let i = 1; i < row; i++)
           // calc first col
           grid[i][0] += grid[i - 1][0]
   
       for(let j = 1; j < col; j++)
           // calc first row
           grid[0][j] += grid[0][j - 1]
   
       for(let i = 1; i < row; i++)
           for(let j = 1; j < col; j++)
               grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])
       
       return grid[row - 1][col - 1]
   };
3. cutie6 commented on Jan 6, 2021

   

   cutie6

   on Jan 6, 2021

   More actions

   这里计算的方向是从右下角到左上角吧
4. fengmiaosen commented on Aug 1, 2022

   

   fengmiaosen

   on Aug 1, 2022

   More actions

   /**
    * 
    * @param {number[][]} grid 
    */
   function minPathSum(grid) {
       if (grid.length < 1 || grid[0].length < 1) {
           return 0
       }
   
       let m = grid.length
       let n = grid[0].length
   
       let dp = new Array(m).fill(undefined).map(() => {
           return new Array(n).fill(0)
       })
   
       for (let i = 0; i < m; i++) {
           for (let j = 0; j < n; j++) {
               // 左上角
               if (i === 0 && j === 0) {
                   dp[0][0] = grid[0][0]
               } 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] = dp[i - 1][j] + grid[i][j]
               } else {
                   dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
               }
           }
       }
   
       return dp[m - 1][n - 1]
   }
5. TonyZhang1993 commented on Feb 5, 2024

   

   TonyZhang1993

   on Feb 5, 2024

   Last edited by TonyZhang1993

   More actions

   看了labuladong 写的 click here

   var minPathSum = function(grid) {
     let m = grid.length
     let n = grid[0].length
     //  备忘录
     let memo = Array.from({length: m}, ()=> Array(n).fill(9999))
   
     //  dp的定义 - 当前坐标最小的路径和
     const dp = (matrix, i, j, memo) => {
       //  处理合法性
       if (i<0 || j<0) {
         return 10000
       }
       //  base case 
       if(i ===0 && j === 0) {
         return matrix[0][0]
       }
       //  备忘录
       if (memo[i][j] !== 9999) {
         return memo[i][j]
       }
       //  当前dp值 = 该点的坐标值 + 左方 和 上方的dp 值
       memo[i][j] = matrix[i][j]+ Math.min(dp(matrix, i-1, j, memo), dp(matrix, i, j-1, memo))
   
       return memo[i][j]
     }
     //  将终点坐标带入
     return dp(grid, m-1, n-1, memo)
   
   };