清晰易懂带注释题解

代码如下：

#include<bits/stdc++.h>

using namespace std;

int n;
int w[110][110];
int dp[110][110];//dp[i][j]=min(dp[i-1][j],dp[i][j-1])+w[i][j];记录从左侧或上方转移过来的最小费用

int main(){
    cin >> n;
    //存图
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> w[i][j];
        }
    }
    //初始化
    for(int j = 1; j <= n; j++){
        dp[0][j] = 1e9;
    }
    for(int i = 1; i <= n; i++){
        dp[i][0] = 1e9;
    }
    //动态规划
    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] = min(dp[i-1][j], dp[i][j-1]) + w[i][j];
            }
        }
    }
    cout << dp[n][n] << "\n";
    return 0;
}