题目18：找出从三角形顶端走到底端的最大和
本帖最后由 欧拉计划 于 2023-8-31 01:11 编辑题目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
视频讲解：
https://www.bilibili.com/video/BV1dp4y1K7MP/
思路解析及源码参考（C & Python）：
**** Hidden Message *****
动态规划{:10_256:}
懒得写 DP 了，写个记忆化搜索吧{:10_269:}
#include <bits/stdc++.h>
using namespace std;
const int n = 15, m = 15;
int a;
int f;
int solve(int i, int j) {
if (f) return f;
if (i == 15) {
return f = a;
}
return f = max(solve(i + 1, j), solve(i + 1, j + 1)) + a;
}
int main() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
scanf("%d", &a);
}
}
printf("%d\n", solve(1, 1));
return 0;
}
1074 好 欧拉！拉拉！打卡！好咯 内容很棒，学到了 感觉写的很不错哦 学到了，收获很大 学到了 每天打卡 1074 还学不懂 学到了学到了! 学习到了，收获很大 学习到了小师妹！ 本帖最后由 每天提高一点点 于 2023-12-20 22:11 编辑
很好的帖子！ nice 加油！！！ 今天也要加油学习！ 加油，很好的帖子！ 视频看懵了
页:
[1]
2