本文共 1482 字，大约阅读时间需要 4 分钟。

1. 问题描述：

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。 对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过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

2. 思路分析：

分析题目可以知道这道题目与之前常规的数字三角形题目是类似的，只是这道题目多了一个限制条件就是在向左下与右下走的次数相差是不能够超过1的，其实这道题目解题得到关键点也在这里，后面看了一些网上的思路然后自己画几个简单的例子尝试能够走的路径，最终可以发现答案与我们输入的N的奇偶性是有关的，当输入的N为奇数的时候，最终的答案是dp[n - 1][n // 2]，为偶数的时候时候为max(dp[n - 1][n // 2 - 1], dp[n - 1][n // 2])，也就是最中间两个值中的较大值，下面N分别是偶数与奇数的时候可以走的路径（图中的数字表示是第几个的数字），可以发现最终答案是在原来的数字三角形得到的dp数组中最后一行的中间位置dp值。所以根据题目的限制条件可以走的路径就变得有限了。所以有的时候还要根据题目的条件多画画图找找突破口在哪里，画出简单例子的图之后那么就可以找到某些规律

3. 代码如下：

if __name__ == '__main__':    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]    # print(dp)    # 最后判断n是奇数还是偶数来返回对应的值    # 奇数肯定是最中间的那个值偶数肯定是中间两个较大值    print(dp[n - 1][n // 2] if n % 2 == 1 else max(dp[n - 1][n // 2 - 1], dp[n - 1][n // 2]))

 

转载地址：http://uuwg.baihongyu.com/