POJ_1163 The Triangle

問題
解法
動的計画法を使う。
三角形を高さiの二次元配列に入れたとき、漸化式は
dp[i][j] = triabgle[i][j] + max(dp[i-1][j], dp[i-1][j-1])

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 101;
int tri[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];
int N;
int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		for(int j = 0; j < i + 1; j++)
			scanf("%d", &tri[i][j]);
		for(int j = N; j < MAX_N; j++)
			tri[i][j] = -1;
	}
	//DP
	dp[0][0] = tri[0][0];
	for(int i = 1; i < N; i++){
		for(int j = 0; j < i + 1; j++){
			dp[i][j] = tri[i][j] + max(dp[i-1][j], dp[i-1][j-1]);
		}
	}
	int ans = 0;
	for(int i = 0; i < N; i++){
		ans = max(ans, dp[N-1][i]);
	}
	printf("%d\n", ans);
	return 0;
}