3217 - Trepte 2.2

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 se afla 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 ≤ 1.000.000; 1 ≤ k ≤ n - 1; deoarece numărul va fi prea mare sa va afișa modulo 9001; la început, persoana se află pe treapta 1. ==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

Rezolvare

def numar_moduri_urcare_trepte(n, k):

   mod = 9001

   # Inițializare vector dp
   dp = [0] * (n + 1)
   dp[1] = 1

   # Calcul numărul de moduri
   for i in range(1, n + 1):
       for j in range(1, k + 1):
           if i + j <= n:
               dp[i + j] = (dp[i + j] + dp[i]) % mod

   return dp[n]

Citire date de intrare

n, k = map(int, input().split())

Calcul și afișare rezultat

result = numar_moduri_urcare_trepte(n, k) print(result)