给定m * n的矩阵,从右下角开始移动,每次移动一步,向左或者向上
k为奇数,选择两个方向较大值,相等向左
k为偶数,选择两个方向较小值,相等向上
记录一下路径确定的模拟方式,非线性DP!!!
#include<iostream>
#include<vector>
using namespace std;
// vector<vector<int>> matrix {{2,5,2,1,3,2}, {3,4,1,3,4,8}, {2,7,5,2,6,4}, {5,7,8,0,9,5}, {1,5,7,8,3,6}};
vector<vector<int>> matrix {{8,9,5,6,2,3,2,3}, {2,3,2,6,5,21,3,5}, {5,9,2,6,5,98,9,3}};
int main()
{
int m = matrix.size()-1;
int n = matrix[0].size()-1;
int ans=matrix[m][n];
for(int k=1;;k++)
{
if(m<=0 || n<=0) break;
if(k%2)
{
if(matrix[m][n-1]>=matrix[m-1][n])
n--;
else
m--;
ans +=matrix[m][n];
}
else
{
if(matrix[m][n-1]>=matrix[m-1][n])
m--;
else
n--;
ans +=matrix[m][n];
}
}
cout<<ans<<endl;
return 0;
}