蓝桥杯505--数字三角形

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入描述

输入的第一行包含一个整数 N (1≤N≤100)，表示三角形的行数。

下面的N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出

27

n = int(input())   # 输入行数
list_1 = [list(map(int, input().split())) for i in range(n)]    # 录入数字三角形

for i in range(1, n):       # 第一行的数字是唯一的，所以需要遍历剩下的n-1行，即从第二行开始
    for x in range(i+1):    # 遍历每一行的数字，数字与行数相对应；i是从一开始的，而遍历是从第二行开始的所以i+1
        if x == 0:          # 若x为0，则代表的是每一行最左侧的数字；所以它是由它的右上侧的数字而来
            list_1[i][x] += list_1[i-1][x]   # 由三角形可知，它的右上侧其实也就是上一行的最左侧，则x是一样的
        elif x == i:        # 若x为1，则代表的是每一行最右侧的数字；所以它是由它的左上侧的数字而来
            list_1[i][x] += list_1[i-1][x-1]  # 由三角形可知，它的左上侧其实也就是上一行的最右侧，由于上一行要比下一行少一个数字，所以它的左上侧为x-1
        else:               # 若x为其他的，代表的是中间的那部分
            list_1[i][x] += max(list_1[i-1][x-1], list_1[i-1][x])  # 它既有左上侧也有右上侧，取两者中最大的
if (n % 2) == 1:            # 若行数为奇数，由题意可知最后一个数字只能为最后一行的最中间的那个，即输出最中间的那个数所代表的和即可
    print(list_1[n-1][n//2])
if (n % 2) == 0:            # 若行数为偶数，由题意可知最后一个数为中间的两个数，则取两个中的最大值即可
    print(max(list_1[n-1][n//2], list_1[n-1][(n//2)-1]))

 解题思路：本题首先需要输入数字三角形；然后通过遍历和累加的方法，算出每一条路的结果；最后根据题目要求输出结果。

最主要的是遍历的时候累加，需要找到相对应的规律。