динамическое программирование снизу вверх

Question

Я пытался написать динамическое программирование, которое подсчитывает количество путей, которыми дорога может быть проложена, используя камни длиной 2, 3, 5 метра.Когда я поставил 2, это дало мне ошибку и, начиная с 2 до 20, должно было дать вывод

1, 1, 1, 3, 2, 5, 6, 8,14, 16, 27, 36, 51, 77, 103, 155, 216, 309, 448

Мой код дает этот результат, когда я начинаю ввод с 3. Я что-то здесь неправильно понял?

def waysRoad(n):
    if n<0:
        return 0

    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 0
    for i in range(2, n):
        sum = 0
        if i >=2:
            sum += dp[i-2]

        if i >=3:
            sum += dp[i-3]
        if i >=5:
            sum += dp[i-5]
        dp[i] = sum
    return dp[i]

Answer 1

Чтобы заполнить n-th запись списка, вам нужно использовать ограничение цикла n+1:

for i in range(2, n + 1):

, также стоит изменить возврат на

return dp[n]