POJ 1163 - The Triangle

http://poj.org/problem?id=1163

概要

長さ N の三角形に並べられた数字が与えられる． 一番上からスタートして左斜め下か右斜め下に移動しながら数を足していったとき，最終的な和の最大値を答える．

制約

• 1 < N <= 100
• 0 <= 数値 <= 99

解法

典型的なDP．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main(void)
 6 {
 7   int N;
 8   cin >> N;
 9   vector<vector<int> > v(N, vector<int>(N));
10   for (int i = 0; i < N; i++) {
11     for (int j = 0; j <= i; j++) {
12       cin >> v[i][j];
13     }
14   }
15   for (int i = N-2; i >= 0; i--) {
16     for (int j = 0; j <= i; j++) {
17       v[i][j] += max(v[i+1][j], v[i+1][j+1]);
18     }
19   }
20   cout << v[0][0] << endl;
21   return 0;
22 }