Python 蓝桥杯 部分测试用例不通过

Question

题目链接: https://www.lanqiao.cn/problems/505/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=3

import os
import sys

# 请在此输入您的代码

N = eval(input())
tri = [list(map(int,input().split())) for x in range(N)]
dp = tri

for i in range(1, N):
  for j in range(i + 1):
    if j == 0:   # 第一列
      dp[i][j] = dp[i - 1][j] + tri[i][j]
    elif j == i:   # 最后一列
      dp[i][j] = dp[i - 1][j - 1] + tri[i][j]
    else:
      dp[i][j] = max(dp[i - 1][j -1], dp[i - 1][j]) + tri[i][j]

print(max(dp[-1]))

我的想法是dp[i][j]用来存储到达数字三角形的(i, j)位置的最大和， 题目要求求出到达底部的最大和，那么就是dp的最后一行中最大的元素，即max(dp[-1])， 但是结果表明只有20%的用例通过。

问题出现在哪里？

Answer 1

你的思路没问题，但是审题不仔细：“此外，向左下走的次数与向右下走的次数相差不能超过 1。”
这句话使得本题最后的结果只能落在最后一行的中位数上。

在你的代码的基础上修改一下最后输出的部分就没问题了：

N = eval(input())
tri = [list(map(int,input().split())) for x in range(N)]
dp = tri

for i in range(1, N):
  for j in range(i + 1):
    if j == 0:   # 第一列
      dp[i][j] = dp[i - 1][j] + tri[i][j]
    elif j == i:   # 最后一列
      dp[i][j] = dp[i - 1][j - 1] + tri[i][j]
    else:
      dp[i][j] = max(dp[i - 1][j -1], dp[i - 1][j]) + tri[i][j]

if N & 1:
  print((dp[-1][N//2]))
else:
  print(max(dp[-1][N//2], dp[-1][(N//2)-1]))