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]
};
複制代碼      

題目反思

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