projecteuler.net

Maximum path sum I

Problem 18 Published on Friday, 5th October 2001, 06:00 pm; Solved by 712990;
Difficulty rating: 5%

Bằng cách bắt đầu ở trên đỉnh của tam giác và di chuyển tới những số liền kề ở hàng dưới, tổng lớn nhất từ trên xuống dưới là 23.

3
7 4
2 4 6
8 5 9 3

Đó là, 3 + 7 + 4 + 9 = 23.

Tìm tổng lớn nhất từ trên xuống dưới của tam giác dưới đây:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

CHÚ Ý: Vì chỉ có tất cả 16384 cách di chuyển nên hoàn toàn giải bài này bằng cách thử mọi cách. Tuy nhiên, Problem 67, cũng là chung một đề với một tam giác chứa 1000 hàng; do đó không thể giải quyết bằng cách "BRUTE FORCE", và đòi hỏi một cách thông minh! ;o)