Re: [閒聊] 每日LeetCode
931. Minimum Falling Path Sum
給予一個n*n矩陣，求出自頂到下的最小路徑和，路徑上到下可由座標(x,y)移動到(x+1,y)
(x+1,y+1)和(x+1,y-1)，對應了中、左、右。
Example :
藍色為最小路徑（可能不唯一）
https://assets.leetcode.com/uploads/2021/11/03/failing1-grid.jpg
思路：
1.找最小路徑問題可以用dfs求解，並用動態規劃優化。
2.任意一個點的最小路徑一定是前三條路徑裡面最小的那一個，狀態轉移方程：
dp(i,j) = mat[i,j] + min(dp(i+1,j), dp(i+1,j+1), dp(i+1,j-1))
3.有動態轉移方程後就可以求dp了，我們初始化最後一行的數值為矩陣值，因為
他的下面沒路可走了。
（因為我是遞迴改過來的所以我從下往上建立dp，由上往下道理差不多。）
4.照動態轉移方程建完dp之後，第一行的值為到達這一個點的最小路徑和，我們只要
再遍歷這一行就能找出最小路徑和了。
Java Code：
-----------------------------------
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
int[][] dp = new int[n][n];
// 初始化
for (int i = 0; i < n; i++) {
dp[n - 1][i] = matrix[n - 1][i];
}
for (int r = n - 2; r >= 0; r--) {
for (int c = 0; c < n; c++) {
if (c == 0) {
dp[r][c] = matrix[r][c] + Math.min(dp[r + 1][c], dp[r +
1][c + 1]);
} else if (c == n - 1) {
dp[r][c] = matrix[r][c] + Math.min(dp[r + 1][c], dp[r +
1][c - 1]);
} else {
dp[r][c] = matrix[r][c] + Math.min(dp[r + 1][c],
Math.min(dp[r + 1][c + 1], dp[r + 1][c - 1]));
}
}
}
int min = dp[0][0];
for (int i = 1; i < n; i++) {
min = Math.min(min, dp[0][i]);
}
return min;
}
}
-----------------------------------
--
https://i.imgur.com/sjdGOE3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.14.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670903974.A.FA5.html
※ 編輯: Rushia (36.231.14.41 臺灣), 12/13/2022 12:01:48
推
12/13 12:02,
3年前
, 1F
12/13 12:02, 1F
→
12/13 12:06,
3年前
, 2F
12/13 12:06, 2F
討論串 (同標題文章)
完整討論串 (本文為第 135 之 719 篇)：