project euler 18,67

問題

3
7 4
2 4 6
8 5 9 3
のような数字のピラミッドが与えられる。
このとき、一番上からスタートし、下に向かって左右のどちらかの数値を選びながら下っていく。
一番下まで来たとき、通ったルートの合計値を最大にするようなルートの値を求める。
上の例の場合、3->7->4->9の23が答え。

考え方

dp。

各数値までのルートでの最大値を覚えておくだけ。