题解 | 数字三角形

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 600;
//const int MOD = 998244353;

ll dp[N][N];

int main(){
	int n;  cin >> n;
	
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= i ; j++){
			cin >> dp[i][j];
		}
	}
	
	
	
	for(int i=1 ; i <= n ; i++){
		for(int j=1 ; j <= i ; j++){
			if(j == 1){
				dp[i][j] += dp[i-1][j];
			}
			else if(i == j){
				dp[i][j] += dp[i-1][j-1];
			}
			else{
				dp[i][j] += max(dp[i-1][j-1],dp[i-1][j]);
			}
		}
	}
	
	ll ans = dp[n][1];
	
	for(int i=2 ; i <= n ; i++){
		ans = max(ans,dp[n][i]);
	}
	
	cout << ans;
	
	return 0;
}