1

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

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

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

В первой строке содержится натуральное число 𝑁 — количество ступеней лестницы (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))
10
  • 1) Какой алгоритм использован? (что-то ваш простовато выглядит, возможно, по времени вылетаете). 2) Какая ошибка написана по результатам теста? 3) ССылку на тест дайте здесь, пожалуйста. Что за сайт? 6 авг 2022 в 20:05
  • 1
    Сама задача из acmp.ru
    – 4500zenja
    6 авг 2022 в 20:06
  • В Питоне по умолчанию ограничение на 1000 рекурсивных вызовов. docs.python.org/3/library/sys.html#sys.setrecursionlimit 6 авг 2022 в 20:33
  • 1
    @Сергей, "я натыкался" - не аргумент. Аргумент - сравнение времен рекурсивного и итеративного варианта или сравнение времен input c sys.stdin.readline. Я предполагаю что вы не сможете получить никакой значимой разницы на этой задаче. В моих тестах все варианты работают 25ms - время загрузки интерпретатора в память. 6 авг 2022 в 20:52
  • 1
    @4500zenja, нет, не оттуда. Задача такая, но формат вывода там другой. Откуда угодно может быть, например, на stepic она же и с правильным выводом, но там вообще все тесты проходят кода из вопроса, вообще без исправлений. 7 авг 2022 в 11:16

2 ответа 2

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)

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

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

2
  • Спасибо большое! 7 авг 2022 в 16:10
  • Сколько интересного у Станислава часто в ответах, я просто восхищён:-) 7 авг 2022 в 16:13
0

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

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

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

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

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])
1
  • Если ответ был полезным, его можно отметить плюсом (нажать треугольник вверх слева от вопроса). Если ответ решил поставленный вопрос - принять ответ (нажать на галку под треугольниками слева). Можно и то, и другое, если ещё и понравилось:-) 6 авг 2022 в 20:17

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.