題目描述
解題思路
本題是動态規劃的經典例題,是一道必須掌握的習題。
- 核心的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]
- 處理邊界條件
題目中明确說了,移動的時候,隻能向右或者向下移動,其他的移動方式是不被允許的,是以對第一行來說,元素隻能從左往右移動,對第一列來說,元素隻能從上往下移動。
- 第一行的處理方法
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];
}
複制代碼
- 處理一般情況
一般情況就是使用我們第一步的核心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]
};
複制代碼
題目反思
- 學會使用動态規劃來求解路徑問題。
- 在動态規劃中處理好邊界條件是很重要的。