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

题目链接: 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%的用例通过。

问题出现在哪里？

你的思路没问题，但是审题不仔细：“此外，向左下走的次数与向右下走的次数相差不能超过 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]))

不知道你这个问题是否已经解决, 如果还没有解决的话:

你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7476574
我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：Python解决DP问题之背包问题
除此之外, 这篇博客: 2021年第十二届蓝桥杯省赛Python组（真题+解析+代码）：路径中的 第三步：弄清dp[i]遍历的顺序 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
```
for i in range(1,n+1):          #先遍历结点a：遍历结点1~n
    for j in range(i+1,i+22):   #再遍历结点b：遍历结点i+1~i+21
```

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

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

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