题解

数塔的升级版，（i，j）位置可以有（i+1，j）（i+1，j+1），（i+1，j+2）走过来，也就是取走到这三个位置的最小值

#include<bits/stdc++.h>
using namespace std;
const int N = 300;
int n, a[N][N], dp[N][N]; 
int main(){
    cin >> n;
    for(int i =1;i <= n;i++){
        for(int j = 1;j <= 2 * i - 1;j++)
            cin >> a[i][j];
    }
    for(int i = n;i >= 1;i--){
        for(int j = 1;j <= 2 * i-1;j++)
            dp[i][j] = min(min(dp[i + 1][j],dp[i + 1][j + 2]),dp[i + 1][j + 1]) + a[i][j];
    }
    cout << dp[1][1];
    return 0;
}