本文共 1919 字，大约阅读时间需要 6 分钟。
为了解决这个问题，我们需要找到数字三角形中从顶部到底部的路径，使得路径上的数字之和最大。路径的选择有两个限制条件：每一步只能向左下或右下移动，并且向左下和向右下走的次数之差不能超过1。
问题分析：我们需要找到从顶部到底部的路径，使得路径上的数字之和最大。由于路径的选择受限制，我们需要动态规划来处理每一种可能的路径。
动态规划状态定义：定义 dp[i][j][k] 为到达第 i 层第 j 个位置时，已经向左下走了 k 次的最大和。
状态转移：对于每一个位置 (i, j, k)，它可以从上一层的两个位置 (i-1, j-1, k-1) 或者 `(i-1, j, k)`` 转移而来。我们需要检查这些转移是否符合路径次数差的限制条件。
初始条件：顶部的位置 dp[0][0][0] 初始化为矩阵顶部的值。
结果计算：根据三角形行数 n 的奇偶性，确定最终结果。奇数行时，结果在中间位置；偶数行时，结果在中间两个位置中的最大值。
n = int(input())matrix = []for _ in range(n): row = list(map(int, input().split())) matrix.append(row)if n == 1: print(matrix[0][0]) exit()# 初始化DP数组dp_prev = [[-1 for _ in range(n)] for __ in range(n)]dp_prev[0][0] = matrix[0][0]for i in range(1, n): dp_current = [[-1 for _ in range(n)] for __ in range(n)] for j in range(i + 1): for k in range(0, i + 1): max_val = -1 # 从左下走来 if j >= 1 and k >= 1: if (k - 1) <= (i - 1) // 2: if dp_prev[j - 1][k - 1] != -1: candidate = dp_prev[j - 1][k - 1] + matrix[i][j] if candidate > max_val: max_val = candidate # 从右下走来 if k <= (i - 1) // 2: if dp_prev[j][k] != -1: candidate = dp_prev[j][k] + matrix[i][j] if candidate > max_val: max_val = candidate if max_val != -1: dp_current[j][k] = max_val else: dp_current[j][k] = -1 dp_prev = dp_current# 确定中间的位置if n % 2 == 1: mid = n // 2 print(dp_prev[mid][mid])else: mid = n // 2 option1 = dp_prev[mid][mid] option2 = dp_prev[mid - 1][mid] print(max(option1, option2))
n 和每一行的数字。dp_prev，顶部位置的值设为矩阵顶部的值。i 和每个位置 j，遍历所有可能的左下次数 k，计算从上一层的两个可能位置转移而来的最大值，并检查路径次数差的限制条件。n 的奇偶性，确定最终结果的位置并输出最大值。这个方法确保了在满足路径选择限制的情况下，找到最大的数字之和。
转载地址：http://uuwg.baihongyu.com/