板子题

/*
 * @Author: YMYS
 * @Date: 2024-12-17 10:06:54
 * @LastEditTime: 2024-12-17 10:40:50
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\1.数字三角形模型\2.最低通行费.cpp
 * @URL:https://www.acwing.com/problem/content/1020/
 * @Description: 1018. 最低通行费
 */
#include<bits/stdc++.h>

#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const int N = 110;

int t;
int f[N][N], dp[N][N];

int T;
void solve(){
    cin>>t;

    // memset(dp, INF, sizeof(dp));

    for(int i=1;i<=t;i++){
        for(int j=1;j<=t;j++){
            cin>>f[i][j];
        }
    }

    //先把最左列和最上行弄好
    for(int i=1;i<=t;i++) dp[i][1] = dp[i-1][1] + f[i][1];
    for(int i=1;i<=t;i++) dp[1][i] = dp[1][i-1] + f[1][i];

    //然后按行开始遍历
    for(int i=2;i<=t;i++){
        for(int j=2;j<=t;j++){
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + f[i][j];
        }
    }

    cout<<dp[t][t]<<endl;
}

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    // cin>>T;
    // while(T--){
        solve();
    // }

    return 0;
}