Question

Programare dinamica
------------------------------------
Cerința
O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial este pe treapta 1)

Date de intrare
Programul citește de la tastatură numerele n și k.

Date de ieșire
Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte.

Restricții și precizări
1 < n ≤ 100.000
1 ≤ k ≤ n - 1
deoarece numărul va fi prea mare sa va afișa modulo 9001.
Exemplul 1:
Intrare

2 2
Ieșire

1
Explicație
Există o soluție, aceea când sare direct pe treapta 2.

Exemplul 2:
Intrare

4 2
Ieșire

3
Explicație
Prima: 1 -> 2 -> 3 -> 4
A doua: 1 -> 2 -> 4
A treia: 1 -> 3 -> 4

Answer 1

#include <iostream>
using namespace std;int v[100002], n , k, nr;int solutie(int x){    return (v[x] == n);}int valid(int x){    if (x > 1)        {            for (int i = 1; i < x; i++)                if (v[x] == v[i]) return 0;            if (v[x - 1] > v[x]) return 0;            if (v[x] - v[x- 1] > k) return 0;        }    return 1;}void Back(int x){    for (int  i = 1; i <= n; i++)    {        v[x] = i;        if (valid(x))            if (solutie(x))                nr++;            else Back(x + 1);    }}int main(){    cin >> n >> k; v[1] = 1; Back(2);    cout << nr;    return 0;}