用python写的递归，为什么会超时啊

Seirin @ 2022-03-24 15:47:02

n = int(input())
v=[]
for i in range (n):
    v.append(list(map(int,input().split())))
def find(i,j):
    if i+1==n:
        return v[i][j]
    else:
        return (max(find(i+1,j),find(i+1,j+1))+v[i][j])

print(find(0,0))

by Terrible @ 2022-03-24 15:56:22

@Seirin

不超时才奇怪吧，你也不看看数据量。

第一层调用 1 次，第二层调用 2 次，第三层就要调用 4 次，\cdots\cdots，第 n 层就要调用 2^{n-1} 次。

应该写成记忆化搜索、递推（dp）的形式才可以吧。

by Seirin @ 2022-03-24 16:22:03

@Terrible 确实 我的问题

by KS_tips_CN @ 2022-03-24 17:08:45

这题可以用递推的方式在一个输入中就做完

每次输入一个值，用一个数组记录到这个位置为止的最长路径长度，由题意，由这个位置上面两个位置的最长路径长度更新就可以

然后就可以在输入的时候顺便处理掉这个位置的最长路径，顺便更新一下总的路径最大值，就可以在输入完成之后直接输出结果了qwq