题目18：找出从三角形顶端走到底端的最大和

欧拉计划

题目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:

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

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)

题目翻译：

从三角形的顶端开始，向着往下一行的相邻数字移动，从起始到结束的最大总和为 23。

3
7 4
2 4 6
8 5 9 3

也就是 3 + 7 + 4 + 9 = 23。

那么，请找出从以下三角形的顶端走到底端的最大总和：

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

视频讲解：




思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

zhangjinxuan

动态规划

懒得写 DP 了，写个记忆化搜索吧

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int n = 15, m = 15;
   
5. int a[n+1][m+1];
   
6. int f[n+1][m+1];
   
7. 
   
8. int solve(int i, int j) {
   
9.         if (f[i][j]) return f[i][j];
   
10.         if (i == 15) {
    
11.                 return f[i][j] = a[i][j];
    
12.         }
    
13.         return f[i][j] = max(solve(i + 1, j), solve(i + 1, j + 1)) + a[i][j];
    
14. }
    
15. 
    
16. int main() {
    
17.         for (int i = 1; i <= n; ++i) {
    
18.                 for (int j = 1; j <= i; ++j) {
    
19.                         scanf("%d", &a[i][j]);
    
20.                 }
    
21.         }
    
22.         printf("%d\n", solve(1, 1));
    
23.     return 0;
    
24. }

复制代码

1074

nkysp

好

1909997160

欧拉！拉拉！打卡！好咯

想个好名字@

内容很棒，学到了

Zhuct

感觉写的很不错哦

夜色枭姬

学到了，收获很大

yasi

学到了

17620892658

每天打卡

clollipops

1074

liangying1980

还学不懂

Pioneer.

学到了学到了!

大魔王666

学习到了，收获很大

疯狗马德森

学习到了小师妹！

每天提高一点点

很好的帖子！

MoistenLe

nice

忘川hd

加油！！！

125800

今天也要加油学习！

陶远航

加油，很好的帖子！

549246531

视频看懵了