AcWing 1018. 最低通行费

#include<iostream>
using namespace std ;
const int N=110,INF=1e9;
int dp[N][N],w[N][N];
int 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++)
        for(int j=1; j<=n; j++) {
            if(i==1&&j==1)//因为这个题是取最小值，所以要特判边界 
                dp[i][j]=w[i][j];
            else {
                dp[i][j]=INF;//先给最大 
                if(i>1) dp[i][j]=min(dp[i][j],dp[i-1][j]+w[i][j]);
                if(j>1) dp[i][j]=min(dp[i][j],dp[i][j-1]+w[i][j]);
            }
        }
    cout<<dp[n][n]<<endl;
    return 0;
}