Pripreme za algoritme(6)

Danas ćemo proći dinamičko programiranje. Evo nam teksta zadatka:  Mali Darko na putu do škole ima 5 stepenica, na koliko različitih načina može prijeći te stepenice ako jednu ili dvije stepenice može prijeći u jednome koraku.
Sada trebamo malo mislit naravno. Ok, znači ovako ćemo. Dinamičko programiranje najlakše zapamtite da ono uvijek nešto sprema i da vam zato treba polje i dinamičko programiranje se koristi kada tražite najmanji ili najveći broj načina. Tako ćemo ovdje imati polje, samo još trebamo smisliti što ćemo u njega spremati. Darko može 1 stepenicu preći na 1 način, 2 stepenica na 2 načina, 3 stepenice na 3 načina itd.Tako ćemo imati polje u kojem će biti spremljeno za koliko se načina može doći do određene stepenice.
  Uzmimo da Darko treba doći do N-te stepenice, a može napraviti od 1 do K stepenica u jednom skoku. Funkcija f će nam vratiti broj načina koji se može doći do neke stepenice pa vidimo ovo:
f(n)=f(n-1)+f(n-2)+f(n-3)...+f(n-k)

Kodom u C++ dobivamo ovo:
#include <stdio.h>
#include <stdlib.h>
int dp[100001];
int a,b,c,d,e,f;
int main()
{
    scanf("%d%d",&a,&b);
    dp[0]=1;
    for(int z=1;z<=a;++z)
    {
            for(int za=1;za<=b;++za)
            {
                    if(z>=za)
                    {
                             dp[z]+=dp[z-za];
                             dp[z]%=1021987;
                    }
            }
    }
    printf("%d",dp[a]);
}
Modanje u kodu ne trebate pisati osim ako nije nužno navedeno u zadatku. Ono se stavlja kada imate prevelike brojeve.
Pozdrav, ;-)