Re: [閒聊] 每日leetcode
1289. Minimum Failing Path Sum II
今天是Hard 的題目 第一眼直覺是dp
min path row i = min(grid[i][j] + min path row i - 1) where j is in a different
column
所以實際上只需要儲存最小跟次小的min path
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& grid) {
int ans = 0;
int min_n = 0, min_j = 0, min_n1 = 0;
for(int i = 0; i < grid.size(); i++){
int next_min_n = INT_MAX, next_min_j = 0, next_min_n1 = INT_MAX;
for(int j = 0; j < grid.size(); j++){
if(j == min_j)
grid[i][j] += min_n1;
else
grid[i][j] += min_n;
if(grid[i][j] <= next_min_n) {
next_min_n1 = next_min_n;
next_min_n = grid[i][j];
next_min_j = j;
}
else if(grid[i][j] < next_min_n1){
next_min_n1 = grid[i][j];
}
}
min_n = next_min_n;
min_n1 = next_min_n1;
min_j = next_min_j;
}
return min_n;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.16.136 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714094068.A.AC0.html
→
04/26 09:15,
2周前
, 1F
04/26 09:15, 1F
推
04/26 09:18,
2周前
, 2F
04/26 09:18, 2F
推
04/26 09:19,
2周前
, 3F
04/26 09:19, 3F
推
04/26 09:21,
2周前
, 4F
04/26 09:21, 4F
推
04/26 09:22,
2周前
, 5F
04/26 09:22, 5F
推
04/26 09:28,
2周前
, 6F
04/26 09:28, 6F
→
04/26 10:15,
2周前
, 7F
04/26 10:15, 7F
討論串 (同標題文章)