数塔升级版题解

数塔升级版题解
正方向遍历求解

#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000;
int n,a[305][705],dp[305][705];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=2*i-1;j++)
            cin>>a[i][j];
    memset(dp,INF,sizeof(dp));
    dp[1][1] = a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=2*i-1;j++)
            dp[i][j] = min({ dp[i-1][j] , dp[i-1][j-2] , dp[i-1][j-1]}) + a[i][j];
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=2*i-1;j++)
    //         cout<<dp[i][j]<<' ';
    //     cout<<endl;
    // }
    int ans = 1e9;
    for(int i=1;i<=2*n-1;i++)
        ans = min(ans,dp[n][i]);
    cout<<ans;
    return 0;
}