Лесенка Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны

Лесенка Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Так же он поступает и дальше, пока не достигнет N -ой ступени. Посчитаем сумму всех чисел, написанных на ступенях через которые прошёл Вова. Требуется написать программу, которая определит оптимальный маршрут Вовы, при котором, шагая, он получит наибольшую сумму. Входные данные В первой строке содержится натуральное число N — количество ступеней лестницы (2≤N≤1000) . Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Числа, написанные на ступенях, не превосходят по модулю 1000

n = int(input())
stairs = list(map(int, input().split()))

dp = [0] * n
dp[0] = stairs[0]
dp[1] = stairs[1] + stairs[0]

for i in range(2, n):
    dp[i] = stairs[i] + max(dp[i-1], dp[i-2])

print(dp[n-1])

Код решает задачу о лесенки, где n означает количество ступеней лестницы, stairs является списком чисел для каждой ступени.

Алгоритм использует динамическое программирование. Значения в списке dp представляют максимальную сумму чисел на пути от первой ступени до текущей. Используя формулу dp[i] = stairs[i] + max(dp[i-1], dp[i-2]), мы вычисляем максимальную возможную сумму на каждой ступени.

В конце мы выводим последнее значение из списка dp, что представляет максимальную сумму чисел на пути от первой до последней ступени.