题解 | 矩阵的最小路径和

#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int n,m;
int f[N][N],g[N][N];


int main() {
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {for(int j=1;j<=m;j++)
cin>>g[i][j];
  }
  for(int i=1;i<=n;i++){
  for(int j=1;j<=m;j++)
  {if(i==1)f[i][j]=f[i][j-1]+g[i][j];//特判第一行只能从左边过来
  if(j==1)f[i][j]=f[i-1][j]+g[i][j];//特判第一列只能从上面过来
  if(i!=1&&j!=1)//其他行从右边或上边过来
    f[i][j]=min(f[i-1][j]+g[i][j],f[i][j-1]+g[i][j]);
//cout<<f[i][j]<<' ';


  }//cout<<endl;
  }cout<<f[n][m];
  return 0;

}
// 64 位输出请用 printf("%lld") +-