其实理解题目后,再结合数学常识就会发现这题和摘花生相似度百分之九十九
略微不同的是有些边界问题要处理
#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int a[N][N];
int f[N][N];
int n,m;
//读入矩阵数据
void readmatrix()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
}
//动态规划
void dp()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
}
}
cout<<f[n][n]<<endl;
}
int main()
{
//处理边界问题
memset(f,0x3f,sizeof(f));
f[1][0]=0;
cin >> n ;
readmatrix();
//动态规划
dp();
return 0;
}