→ ray90514: 日常不會命名變數:( 04/26 09:15
推 JIWP: 大師 04/26 09:18
推 sustainer123: 大師 你版剩我不會dp了 04/26 09:19
推 devilkool: 大師，只剩我不會hard了 04/26 09:21
推 argorok: 大師 04/26 09:22
推 SecondRun: 大師 04/26 09:28
→ DJYOSHITAKA: 好羨慕能隨手能寫hard的人：（ 04/26 10:15
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