Project Euler with Ruby on WSL [Problem 18]

関東は暑い

今日この頃です

問題

Maximum path sum I

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3

7 4

2 4 6

8 5 9 3

That is, 3 + 7 + 4 + 9 = 23. Find the maximum total from top to bottom of the triangle below:

(略)

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

私訳

経路上の和の最大値

三角形の上の頂点から始めて、隣接の数の和を一番下まで取る時 最大の合計値を求めよ 注意:全ルート探索はこの問題なら通用するけど問題 67 だとだめだよ

解答方針

移動可能な経路はどこの数字も二つしかない。

そのうち大きいほうに行かないと和も大きくならない つまり、常に大きいほうに行けばいい

でやってみたらだめだった！

解答方針2

その地点までの最大の和を記録していくことにする

3

7 4

2 4 6

8 5 9 3 を 3

10 7

12 14 13

20 19 23 16 と変換するわけだ。上の左右を見ればいいな。