天天看點

LeetCode——最小路徑和(動态規劃)

題目描述

LeetCode——最小路徑和(動态規劃)

解題思路

本題是動态規劃的經典例題,是一道必須掌握的習題。
  1. 核心的DP方程

dp[i][j]=dp[i][j]+Math.min(dp[i−1][j],dp[i][j−1])+dp[i][j]dp[i][j] = dp[i][j] + Math.min(dp[i-1][j],dp[i][j-1]) + dp[i][j]dp[i][j]=dp[i][j]+Math.min(dp[i−1][j],dp[i][j−1])+dp[i][j]

  1. 處理邊界條件
題目中明确說了,移動的時候,隻能向右或者向下移動,其他的移動方式是不被允許的,是以對第一行來說,元素隻能從左往右移動,對第一列來說,元素隻能從上往下移動。
  • 第一行的處理方法
for (let j = 1; j < grid[0].length; j++) {
    grid[0][j] = grid[0][j] + grid[0][j - 1];
}
複制代碼      
  • 第一列的處理方法
for (let i = 1; i < grid.length; i++) {
    grid[i][0] = grid[i][0] + grid[i - 1][0];
}
複制代碼      
  1. 處理一般情況
一般情況就是使用我們第一步的核心DP方程來進行求解。

AC代碼

var minPathSum = function (grid) {
  // 本題堪稱是動态規劃的經典例題,必須背會
  // 本題最核心的動态方程為:dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + dp[i][j]
  // 首先處理邊界條件,題目明确指出每次移動隻能向右或者向下移動,是以不能向左或者其他方向進行移動。
  // 處理第一行的元素:第一行的元素沒有上項,從第一行的第二個元素開始進行處理
  for (let j = 1; j < grid[0].length; j++) {
    grid[0][j] = grid[0][j] + grid[0][j - 1];
  }
  // 處理第一列的元素,道理和處理第一行的元素類似
  for (let i = 1; i < grid.length; i++) {
    grid[i][0] = grid[i][0] + grid[i - 1][0];
  }
  // 處理一般情況
  for (let i = 1; i < grid.length; i++) {
    for (let j = 1; j < grid[0].length; j++) {
      grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
    }
  }
  return grid[grid.length - 1][grid[0].length - 1]
};
複制代碼      

題目反思

  • 學會使用動态規劃來求解路徑問題。
  • 在動态規劃中處理好邊界條件是很重要的。

繼續閱讀