Решаю задачу с codeforces на dp, выдает runtime error

Question

https://codeforces.com/group/LB1sSRhotq/contest/268096/attachments, задача - лестница.

Дан n, и список длиной n.

Мы идем по списку с шагом 1, либо 2 и суммируем числа, в которые попали; надо максимизировать эту сумму.

n = int(input()) 
a = list(map(int, input().split())) 
 
dp = [-1] * (n+2) 
def f(n): 
    if dp[n] != -1: 
        return dp[n] 
    if n == 1: 
        dp[n] = a[0] 
    elif n == 2: 
        dp[n] = max(a[1], a[0]+a[1]) 
    else: 
        dp[n] = max(f(n-1) + a[n-1], f(n-2) + a[n-1]) 
    return dp[n] 
print(f(n))

Вот код, который выдает на 1 тест - 3 (1, [1, 2] -> 3), однако при выполнении кода пишет runtime error, хотя бесконечной рекурсии здесь не может быть, да и глубина рекурсии не более 100, так что я хочу узнать, в чем здесь ошибка.

Answer 1

Восходящее динамическое программирование не требует рекурсии:

dp = [0] * (n+1)
dp[1] = a[0]
for i in range(2,n+1):
    dp[i] = max(dp[i-1], dp[i-2]) + a[i-1]
print(dp[n])

(на Python можно даже убрать вторую строчку и цикл с единицы запустить, т.к. обращение к -1 элементу ничего не испортит)

Answer 2

А ларчик просто открывался. Решения со стандартным входом/выходом не принимаются. Вы обязаны читать задание из файла ladder.in и записывать ответ в файл ladder.out.

Добавлю что задача может быть решена без рекурсии и без массива. Для вычисления максимума следующей ступеньки достаточно знать максимумы двух предыдущих (переменные sp, s):

with open('ladder.in') as f:
    next(f) 
    sp, s = 0, 0
    for ai in map(int, next(f).split()):
        sp, s = s, max(sp, s) + ai

with open('ladder.out', 'w') as f:
    print(s, file=f)

P.S. Задача безобразно поставлена. Наврано в условии, условия приёма отличаются от общепринятых. Немудрено запутаться.

БЛОГ НА HUSL

Решаю задачу с codeforces на dp, выдает runtime error

Ответы (2 шт):