A
A
ALTech12020-08-19 12:06:30
C++ / C#
ALTech1, 2020-08-19 12:06:30

How can I fix my code for solving the "Bunny" problem?

There is such a dynamic programming problem.

Formulation of the problem
Bunny
(Time: 1 sec. Memory: 16 MB Difficulty: 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 нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.


I wrote this code, but it breaks off on the 9th test.
#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;
}


Please tell me what is wrong. I want to solve without recursion.

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question