推 JIWP: 別捲了 04/26 23:29
※ 編輯: DJYOSHITAKA (125.228.146.144 臺灣), 04/26/2024 23:32:57
推 wu10200512: 別卷了 04/26 23:36
1289. Minimum Falling Path Sum II
記下每個row前兩個小的path sum
然後dp下去
若(i,j)正上方剛好==最小那個path sum
就用第二小的path sum
剩肥肥我又臭又長了
int minFallingPathSum(vector<vector<int>>& grid) {
vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));
int num_c = grid[0].size();
int num_r = grid.size();
int min_sum = INT_MAX;
int min_sum_2 = INT_MAX;
//init
for(int j=0; j<num_c; j++)
{
dp[0][j] = grid[0][j];
if(dp[0][j] < min_sum_2)
{
min_sum_2 = dp[0][j];
if(min_sum_2 < min_sum)
swap(min_sum, min_sum_2);
}
}
//dp
for(int i=1; i<num_r; i++)
{
for(int j=0; j<num_c; j++)
{
if(dp[i-1][j] == min_sum)
dp[i][j] = grid[i][j] + min_sum_2;
else
dp[i][j] = grid[i][j] + min_sum;
}
// update min_sum and min_sum_2 of the row
min_sum = INT_MAX;
min_sum_2 = INT_MAX;
for(int j=0; j<num_c; j++)
{
if(dp[i][j] < min_sum_2)
{
min_sum_2 = dp[i][j];
if(min_sum_2 < min_sum)
swap(min_sum, min_sum_2);
}
}
}
return min_sum;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714145352.A.1BC.html