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; }