Лесенки , задача на Python
Лесенка
Вова стоит перед лесенкой из NN ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Так же он поступает и дальше, пока не достигнет NN-ой ступени. Посчитаем сумму всех чисел, написанных на ступенях через которые прошёл Вова.
Требуется написать программу, которая определит оптимальный маршрут Вовы, при котором, шагая, он получит наибольшую сумму.
Входные данные
В первой строке содержится натуральное число NN — количество ступеней лестницы (2≤N≤1000)(2≤N≤1000). Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Числа, написанные на ступенях, не превосходят по модулю 10001000.
Выходные данные
Выведите наибольшее значение суммы.
Мой код, прошел 5 тестов:
n=int(input())
b=list(map(int,input().split()))
dp=[0]*(n)
dp[0]=b[0]
if n>=2:
if dp[0]>0:
dp[1]=dp[0]+b[1]
else:
dp[1]=b[0]
if n==1:
print(dp[0])
elif n==2:
print(dp[1])
else:
for i in range(2,n):
dp[i]=max(dp[i-1],dp[i-2])+b[i]
print(dp[n-1])Рад за тебя. А последнюю ступеньку можно перепрыгнуть?
Тут весь цимес именно в том, лежат ли на последних 3 ступеньках отрицательные числа, и какие. Например, если у нас там 2 -10 -11 -12, то логично было бы идти 2-11, а не выбирать -10 как меньшее зло и оказаться потом еще на -12. Но если -12 неизбежно, тогда алгоритм в конце менять смысла нет.
нашел ошибку
Ваш код почти правильный, но есть небольшая ошибка в логике для n >= 2. Давайте разберём задачу и исправим код.
### Анализ задачи:
1. **Правила перемещения**:
- Можно перейти на следующую ступень (`i+1`).
- Можно перепрыгнуть через одну ступень (`i+2`).
2. **Цель**:
- Найти максимальную сумму чисел на пройденных ступенях.
### Ошибка в вашем коде:
В строке 9: dp[1]=b[0] — это неверно, потому что при n >= 2 Вова может сразу прыгнуть на 2-ю ступень, и тогда dp[1] = b[1] (если b[0] отрицательное).
### Исправленный код:
```python
n = int(input())
b = list(map(int, input().split()))
dp = [0] * n
dp[0] = b[0]
if n >= 2:
dp[1] = max(b[0] + b[1], b[1]) # Выбираем лучший вариант: шагнуть или прыгнуть
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2]) + b[i] # Основная динамика
print(dp[-1])
```
### Пояснения:
1. **Инициализация dp[0]**:
- Если ступень одна (`n == 1`), то ответ — b[0].
2. **Инициализация dp[1]**:
- Если ступеней две (`n >= 2`), Вова может:
- Пройти через обе: b[0] + b[1].
- Прыгнуть сразу на вторую: b[1].
- Выбираем максимум из этих вариантов.
3. **Основной цикл (для i >= 2)**:
- dp[i] — это максимальная сумма до ступени i.
- На каждом шаге выбираем, откуда прийти: с i-1 или i-2.
### Пример:
**Входные данные:**
```
3
1 2 3
```
**Работа кода:**
- dp[0] = 1
- dp[1] = max(1 + 2, 2) = 3
- dp[2] = max(3, 1) + 3 = 6
**Ответ:**
```
6
```
Теперь ваш код должен проходить все тесты! 😊