龙岗英文网站建设自学网网站

链接：

1289. 下降路径最小和 II

题意：

每一行选择一个数字，相邻行选择不能是同一列，求选择的数字和最小是多少

解：

每一行选择最小的次小的，下一行能加最小的（列坐标不冲突）就加最小的，不然就加次小的

虽然写的丑陋了点，但是至少是O(n^2)，蛤蛤

实际代码：

#include<bits/stdc++.h>
using namespace std;
int minFallingPathSum(vector<vector<int>>& grid)
{vector<vector<int>>dp(grid);int lgrow=grid.size(),lgcol=grid[0].size();int Min=-1,MMin=-1;for(int j=0;j<lgcol;j++){if(Min==-1){Min=j;}else{if(dp[0][j]<dp[0][Min]){if(MMin==-1||dp[0][Min]<dp[0][MMin]) MMin=Min;Min=j;}else if(MMin==-1) MMin=j;else if(dp[0][j]<dp[0][MMin]) MMin=j;}}//cout<<Min<<" "<<MMin<<endl;for(int i=1;i<lgrow;i++){int nextMin=-1,nextMMin=-1;for(int j=0;j<lgcol;j++){if(j==Min) dp[i][j]+=dp[i-1][MMin];else dp[i][j]+=dp[i-1][Min];if(nextMin==-1){nextMin=j;}else{if(dp[i][j]<dp[i][nextMin]){if(nextMMin==-1||dp[i][nextMin]<dp[i][nextMMin]) nextMMin=nextMin;nextMin=j;}else if(nextMMin==-1) nextMMin=j;else if(dp[i][j]<dp[i][nextMMin]) nextMMin=j;}}Min=nextMin,MMin=nextMMin;//cout<<Min<<" "<<MMin<<endl;}int ret=INT_MAX;for(int i=0;i<lgrow;i++){ret=min(ret,dp[lgrow-1][i]);}return ret;
}
int main()
{int n;cin>>n;vector<vector<int>> grid;int temp;for(int i=0;i<n;i++){vector<int>t;for(int j=0;j<n;j++){cin>>temp;t.push_back(temp);}grid.push_back(t);}int ans=minFallingPathSum(grid);cout<<ans<<endl;return 0;
}

限制：

• n == grid.length == grid[i].length
• 1 <= n <= 200
• -99 <= grid[i][j] <= 99