• 输入

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

• 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110 , INF = 0x3f3f3f3f;
int dp[N][N],w[N][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)
        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;
}