做网站最好软件,秦皇岛市城乡建设网站,企业网站内使用了哪些网络营销方式,昆明网站建设推广服务链接#xff1a;
1289. 下降路径最小和 II
题意#xff1a;
每一行选择一个数字#xff0c;相邻行选择不能是同一列#xff0c;求选择的数字和最小是多少
解#xff1a;
每一行选择最小的次小的#xff0c;下一行能加最小的#xff08;列坐标不冲突#xff09;就加…链接
1289. 下降路径最小和 II
题意
每一行选择一个数字相邻行选择不能是同一列求选择的数字和最小是多少
解
每一行选择最小的次小的下一行能加最小的列坐标不冲突就加最小的不然就加次小的
虽然写的丑陋了点但是至少是O(n^2)蛤蛤
实际代码
#includebits/stdc.h
using namespace std;
int minFallingPathSum(vectorvectorint grid)
{vectorvectorintdp(grid);int lgrowgrid.size(),lgcolgrid[0].size();int Min-1,MMin-1;for(int j0;jlgcol;j){if(Min-1){Minj;}else{if(dp[0][j]dp[0][Min]){if(MMin-1||dp[0][Min]dp[0][MMin]) MMinMin;Minj;}else if(MMin-1) MMinj;else if(dp[0][j]dp[0][MMin]) MMinj;}}//coutMin MMinendl;for(int i1;ilgrow;i){int nextMin-1,nextMMin-1;for(int j0;jlgcol;j){if(jMin) dp[i][j]dp[i-1][MMin];else dp[i][j]dp[i-1][Min];if(nextMin-1){nextMinj;}else{if(dp[i][j]dp[i][nextMin]){if(nextMMin-1||dp[i][nextMin]dp[i][nextMMin]) nextMMinnextMin;nextMinj;}else if(nextMMin-1) nextMMinj;else if(dp[i][j]dp[i][nextMMin]) nextMMinj;}}MinnextMin,MMinnextMMin;//coutMin MMinendl;}int retINT_MAX;for(int i0;ilgrow;i){retmin(ret,dp[lgrow-1][i]);}return ret;
}
int main()
{int n;cinn;vectorvectorint grid;int temp;for(int i0;in;i){vectorintt;for(int j0;jn;j){cintemp;t.push_back(temp);}grid.push_back(t);}int ansminFallingPathSum(grid);coutansendl;return 0;
}限制
n grid.length grid[i].length1 n 200-99 grid[i][j] 99
