Ваш алгоритм работает хорошо. Проблема с глубиной рекурсии:
$ (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)
Теперь можно обрабатывать лесенки из миллиардов ступенек в постоянной памяти.
Ещё раз - это просто упражнение для ума. Всё что вам действительно нужно от этого ответа - ослабить ограничение на глубину рекурсии. :)
input
csys.stdin.readline
. Я предполагаю что вы не сможете получить никакой значимой разницы на этой задаче. В моих тестах все варианты работают 25ms - время загрузки интерпретатора в память.