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;
}
};