Есть такая задача на динамическое программирование.
Постановка задачиЗайчик
(Время: 1 сек. Память: 16 Мб Сложность: 55%)
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.
Входные данные
В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.
Написал вот такой код, но он обламывается на 9 тесте.
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
int k, n;
cin >> k >> n;
vector<int> dp(n + 2, 0);
dp[0] = 0;
dp[1] = 1;
for (int i = 0; i <= n + 1; i++) {
for (int j = 1; j <= k; j++) {
if (i - j >= 0)
dp[i] += dp[i - j];
}
}
cout << dp[n+1] << endl;
}
Подскажите пожалуйста, что не так. Хочу решить без рекурсии.
