蓝桥杯第十一届省赛——数字三角形（python组）-Toy模板网

这篇具有很好参考价值的文章主要介绍了蓝桥杯第十一届省赛——数字三角形（python组）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：数字三角形

【问题描述】：

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

大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右

边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

【输入格式】

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

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

【输出格式】

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

【样例输入】

3 8

8 1 0

2 7 4 4

4 5 2 6 5

【样例输出】

问题分析

我们的目的是寻求路径的最大和，一步步的往下移，找到每一步的最优解，不由而然我们可以想到动态规划法，此时注意题目的限制条件向左下走的次数与向右下走的次数相差不能超过 1。一次慢慢寻找每一步的最优解（也就是每走一步的最大路径），一直到最后一步的时候，再求出这一步的最优解（也就是最后一步的路径最大值）。

问题答案

    n = int(input())
    matrix = list()
    for i in range(n):
        # 使用map函数将输入的字符串中的数字转为int类型, 使用list方法将其转换为一个列表
        matrix.append(list(map(int, input().split())))
    dp = [[0] * n for i in range(n)]
    dp[0][0] = matrix[0][0]
    for i in range(1, n):
        for j in range(i + 1):
            # 每行第一个元素
            if j == 0:
                dp[i][j] = dp[i - 1][j] + matrix[i][j]
            # 每行最后一个元素
            elif j == i:
                dp[i][j] = dp[i - 1][j - 1] + matrix[i][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j]
    #此时注意题目还有限制条件（往右走和往左走相差不能超过1）
    # 最后判断n是奇数还是偶数来返回对应的值
    # 奇数肯定是最中间的那个值偶数肯定是中间两个较大值
    print(dp[n - 1][n // 2] if n % 2 == 1 else max(dp[n - 1][n // 2 - 1], dp[n - 1][n // 2]))

代码分析

输入数字三角形

    n = int(input())
    matrix = list()
    for i in range(n):

        matrix.append(list(map(int, input().split())))

无容置疑这一段代码是为了输入格式，将需要输入的三角形由矩阵转换成列表

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

如果对代码有什么不懂的地方可以自行查找map，list，split，append函数的解释

生成一个dp全零矩阵---用于保存最优解

    dp = [[0] * n for i in range(n)]
    dp[0][0] = matrix[0][0]

dp = [[0] * n for i in range(n)]很多人会对这个不怎么明白，其实就是生成N x N 的二维矩阵如下：

#n=5时也就是生成这样一个矩阵用来保存每一步dp的最优解
dp = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]

代码过程

蓝桥杯第十一届省赛——数字三角形（python组）

for i in range(1, n):
        for j in range(i + 1):
            # 每行第一个元素
            if j == 0:
                dp[i][j] = dp[i - 1][j] + matrix[i][j]
            # 每行最后一个元素
            elif j == i:
                dp[i][j] = dp[i - 1][j - 1] + matrix[i][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j]

由上图看知道代码的运算过程，可以通过自己带入运算，从我手写的图片可以看出，运算有三种情况，也就是每行开头的第一个数字，还有最后一个数字是不需要比较的，但是当需要比较的那一步比较大的时候我们需要增加一个else，这样就可以得到每一步得最优解。

答案

错误答案

许多人会通过以下代码去寻找最优解，但是忽略了一个条件就是：向左下走的次数与向右下走的次数相差不能超过 1。

print(max(dp[4][0],dp[4][1],dp[4][2],dp[4][3],dp[4][4]))

正确答案

因为这个限制条件，所以当n为奇数得时候那肯定就是最后一步最优解得中间值，如果n为偶数得时候，最优解就要通过中间得两个值进行比较。

#此时注意题目还有限制条件（往右走和往左走相差不能超过1）
    # 最后判断n是奇数还是偶数来返回对应的值
    # 奇数肯定是最中间的那个值偶数肯定是中间两个较大值
    print(dp[n - 1][n // 2] if n % 2 == 1 else max(dp[n - 1][n // 2 - 1], dp[n - 1][n // 2]))