一个商人穿过一个N×N的正方形的网格，去参加一个非常重要的商务活动。
他要从网格的左上角进，右下角出。
每穿越中间1个小方格，都要花费1个单位时间。
商人必须在(2N-1)个单位时间穿越出去。
而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。
输入格式 第一行是一个整数，表示正方形的宽度N。
后面N行，每行N个不大于100的整数，为网格上每个小方格的费用。
输出格式 输出一个整数，表示至少需要的费用。
数据范围 1≤N≤100 输入样例： 5 1 4 6 8 10 2 5 7 15 17 6 8 9 18 20 10 11 12 19 21 20 23 25 29 33 输出样例： 109 样例解释 样例中，最小值为109=1+2+5+7+9+12+19+21+33。
2020-2-24更新 三步走 1.初始化 2.状态转移方程 3.输出答案
#include<bits/stdc++.h> using namespace std; const int N=1000; int f[N][N]; int n; int w[N][N]; int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>w[i][j]; for(int i=1;i<=n;i++) f[0][i]=0x3f3f3f3f; //初始化边界 for(int i=1;i<=n;i++) f[i][0]=0x3f3f3f3f; f[0][1]=f[1][0]=0; 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])+w[i][j]; //递推方程 } cout<<f[n][n]<<endl; //结果答案 }要判断边界
#include<bits/stdc++.h> using namespace std; const int N=110; int a[N][N]; int dp[N][N]; int n; int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==1&&j==1) dp[i][j]=a[i][j]; else { dp[i][j]=0x3f3f3f3f; if(i>1) dp[i][j]=min(dp[i][j],dp[i-1][j]+a[i][j]); if(j>1) dp[i][j]=min(dp[i][j],dp[i][j-1]+a[i][j]); } } cout<<dp[n][n]<<endl; }