POJ1163 The Triangle

問題文

解法：DP(上の二つのやつのでかいほうを足していくだけ)

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
	
	int n;
	
	int t[102][102] = {0};
	int dp[102][102] = {0};
	
	scanf("%d",&n);
	
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= i;j++){
		scanf("%d",&t[i][j]);
		}
	}

	for(int i = 1;i <= n;i++){
		for(int j = 0;j <= i;j++){
		dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + t[i][j];
		}
	}
	
	int ans = 0;
	
	for(int i = 1;i <= n;i++){
	ans = max(ans,dp[n][i]);
	}
	
	printf("%d\n",ans);
	
	return 0;
}