Задача "Лесенка" на Python

Question

Вова стоит перед лесенкой из ? ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Так же он поступает и дальше, пока не достигнет ?-ой ступени. Посчитаем сумму всех чисел, написанных на ступенях через которые прошёл Вова.

Требуется написать программу, которая определит оптимальный маршрут Вовы, при котором, шагая, он получит наибольшую сумму.

Входные данные

В первой строке содержится натуральное число ? — количество ступеней лестницы (2≤?≤1000). Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Числа, написанные на ступенях, не превосходят по модулю 1000

Выходные данные

Выведите наибольшее значение суммы.

Мой код проходит 48 тестов из 50, а затем выдает ошибку. Помогите, пожалуйста, найти ошибку

Сам код:

n = int(input())
a = [0] + list(map(int, input().split()))
dp = ['']*(n+1)

dp[0] = 0
dp[1] = a[1]

def F(n):
    if dp[n] != '':
        return dp[n]
    if n < 2:
        return dp[n]
    dp[n] = max(F(n-1)+a[n], F(n-2)+a[n])
    return dp[n]

print(F(n))

Answer 1

У вас неоптимальны по времени рекурсия и ввод/вывод (input медленнее sys.stdin, а print - sys.stdout).
Особенно рекурсия - избавляйтесь от неё. В то время как можно быстро бежать по списку, вы нагружаете стек.

Рекомендуемая последовательность исправлений (делаете один шаг и проверяете, помогло ли. Если да, то остальные можно не делать):

Возможно, вы вообще "вылетаете" по глубине рекурсии, если N=1000, а даже не по времени. Начните с того, что примените рекомендацию 1 из моего ответа по ссылке ниже, она как раз на такой случай. (надо добавить в код строку sys.setrecursionlimit (5000) и import sys).
Если не поможет - убирайте рекурсию совсем. Или сразу это делайте.
Ниже моё решение, оно должно работать нормально. Сравните со своим, можете таким образом убрать рекурсию.
Замена ввода. Тоже см. моё решение.
Замена вывода.

Возможно, вам тему про оптимальные решения и про недостатки рекурсии имеет смысл еще раз проглядеть. И вот по элиминации рекурсии несколько советов на будущее:
Простые решения проблем с рекурсией

import sys

n = int (input())
list_A = [j for j in map(int, sys.stdin.readline().split())]
list_A.insert(0, None)
list_D = [0, list_A[1]]

if n < 2:
    print (list_D[1])
else:
    for i in range(2, n + 1):
        list_D.append(max (list_D[i-1],list_D[i-2]) + list_A[i])
    print (list_D[n])

Answer 2

Ваш алгоритм работает хорошо. Проблема с глубиной рекурсии:

$ (echo 100 ; seq -s ' ' 100) | python stairs.py
5050

$ (echo 1000 ; seq -s ' ' 1000) | python stairs.py
Traceback (most recent call last):
  File "/home/sv/desk/stackoverflow/temp.py", line 16, in <module>
    print(F(n))
  File "/home/sv/desk/stackoverflow/temp.py", line 13, in F
    dp[n] = max(F(n-1)+a[n], F(n-2)+a[n])
  File "/home/sv/desk/stackoverflow/temp.py", line 13, in F
    dp[n] = max(F(n-1)+a[n], F(n-2)+a[n])
  File "/home/sv/desk/stackoverflow/temp.py", line 13, in F
    dp[n] = max(F(n-1)+a[n], F(n-2)+a[n])
  [Previous line repeated 995 more times]
  File "/home/sv/desk/stackoverflow/temp.py", line 9, in F
    if dp[n] != '':
RecursionError: maximum recursion depth exceeded in comparison

По условиям задачи в лесенке не более 1000 ступенек. В Питоне глубина рекурсии ограничена как раз тысячей вызовов. Совпадение. Что бы исправить, добавьте в начало вашего кода вызов sys.setrecursionlimit:

import sys
sys.setrecursionlimit(2000)


...

$ (echo 1000 ; seq -s ' ' 1000) | python stairs.py
500500

P.S. Заметьте что следующее значение F(n) зависит только от пары предыдущих - F(n - 1) и F(n - 2). Можно обойтись без массива dp. Последовательная обработка поступающих чисел и поддержание в кеше двух последних значений:

input() # пропустить строку, она не нужна
a = 0
b = 0
for c in map(int, input().split()):
    a, b = b, max(a, b) + c
print(b)

P.P.S. предыдущий код всё равно расходует много памяти. Во-первых input() читает целиком строку, во-вторых split() создаёт список слов тоже целиком. В ограничениях задачи это не важно - не более 1000 чисел во второй строке. Но хочется написать алгоритм работающий в константной памяти. Например в C это был бы самый естественный код. Но не в Питоне в котором нет удобного способа читать из входного потока слова, не строки целиком. Исправляем: read_words читает слова по одному используя буфер фиксированного размера (если нет очень длинных слов, в этом случае буфер растягивается). С такой читалкой алгоритм становится действительно потоковым:

import string
import sys


def read_words():
    READ_SIZE = 1024
    WS = str.maketrans(string.whitespace, ' ' * len(string.whitespace))

    tail = ''
    while True:
        block = sys.stdin.read(max(READ_SIZE, len(tail))).translate(WS)
        if len(block) == 0:
            yield from tail.split()
            return
        text = tail + block

        last_ws = text.rfind(' ')
        if last_ws == -1:
            tail = text
            continue

        yield from text[:last_ws].split()
        tail = text[last_ws:]


input()
a = 0
b = 0
for c in map(int, read_words()):
    a, b = b, max(a, b) + c
print(b)

Теперь можно обрабатывать лесенки из миллиардов ступенек в постоянной памяти.

Ещё раз - это просто упражнение для ума. Всё что вам действительно нужно от этого ответа - ослабить ограничение на глубину рекурсии. :)

БЛОГ НА HUSL

Задача "Лесенка" на Python

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