Задача на ДП. Не понимаю в чем ошибка

Question

Сдать решение задачи E-Кузнечик и лягушки Полный балл: 100 Ограничение времени: 2 с Ограничение реального времени: 5 с Ограничение памяти: 256M Задача E: Кузнечик и лягушки Условие задачи (pdf)

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.

На некоторых столбиках сидят лягушки, которые едят кузнечиков (Кузнечик не должен попадать на эти столбики!). Определите, сколькими способами Кузнечик может безопасно добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад. Формат входных данных Входная строка содержит натуральные числа N и K, разделённые пробелом. Гарантируется, что 1≤N,K≤32. Во второй строке записано число лягушек L (0≤L≤N−2). В третьей строка записано L натуральных чисел: номера столбиков, на которых сидят лягушки (среди них нет столбиков с номерами 1 и N).

Примеры
Входные данные
6 4
2
2 4
Выходные данные
3

Не понимаю в чем ошибка не все тесты проходит

n, k = map(int, input().split())
l = int(input())
s_l = list(map(int, input().split()))
dp = [1] * n
dp_1 = []
for i in range(l):
    dp[s_l[i] - 1] = 0
dp_1 = []
dp_1.append(dp[0])
print(dp)
for i in range(1,n):
    if dp[i] == 0:
        pass
    else:
        if i < k:
            dp_1.append(sum(dp_1[:i]))
        else:
            dp_1.append(sum(dp_1[i - k:i]))
print(dp_1[-1])

Answer 1

В dp1 вы не добавляете столбики с лягушками, а значит, будет сбиваться подсчёт по диапазону - i - k будет захватывать более ранние столбики, чем нужно

if dp[i] == 0:
    dp_1.append(0)

P.S. собственно, зачем dp1 нужен вообще?

n, k = map(int, input().split())
l = int(input())
s_l = list(map(int, input().split()))
dp = [1] * n
for i in range(l):
    dp[s_l[i] - 1] = 0
for i in range(1,n):
    if dp[i]:
        if i < k:
            dp[i] = sum(dp[:i])
        else:
            dp[i] = sum(dp[i - k:i])
print(dp[-1])

Следующий шаг, если понадобится оптимизация для больших N (для N=32 можно обойтись) - отказаться от суммирования каждый раз, и находить сумму диапазона через разность накопленных (кумулятивных) сумм.

Для этого по ходу дела суммируем полученные значения dp[] в дополнительный список cumsum[]

cumsum[i] = cumsum[i-1] + dp[i]

а сумма sum(dp[i - k:i]) равна разности cumsum[i-1] -cumsum[i-k-1].

Но более того - в данном случае и отдельный список не нужен. Просто складываем полученные значения, и отнимаем значения с левого конца интервала (пишу прямо здесь, индексы нужно проверить поточнее)

 dp[i] = partsum
 partsum  += dp[i]
 if i >= k:
    partsum -= dp[i-k-1]

БЛОГ НА HUSL

Задача на ДП. Не понимаю в чем ошибка

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