Tämän ja seuraavan viikon tehtävien aiheena on dynaaminen ohjelmointi. Jos et tunne tekniikkaa ennestään, sopiva johdatus aiheeseen on Tirakirjan luku 9.

Merkkijonojen laskeminen

Tyypillinen dynaamisen ohjelmoinnin sovellus on laskea, monellako $n$ merkin pituisella merkkijonolla (tai $n$ alkion kokoisella taulukolla) on haluttu ominaisuus. Tällöin ongelman voi koettaa esittää rekursiivisena funktiona $f(n)$, joka antaa ratkaisun tapauksessa $n$.

Tarkastellaan esimerkkinä tehtävää, jossa haluamme laskea $n$-pituiset bittijonot, joissa ei ole missään kohdassa kolmea samaa bittiä peräkkäin. Merkitään $f(n)$:llä tällaisten bittijonojen määrää. Esimerkiksi $f(3)=6$, koska mahdolliset bittijonot ovat 001, 010, 011, 100, 101 ja 110.

Funktion pohjatapaukset ovat $f(1)=2$ ja $f(2)=4$. Tämän jälkeen suurempia tapauksia voi laskea kaavalla $f(n)=f(n-1)+f(n-2)$. Tässä on ideana laskea yhteen tapaukset, joissa bittijonon lopussa on $1$ tai $2$ samaa bittiä. Voimme toteuttaa laskennan tehokkaasti dynaamisella ohjelmoinnilla näin:

f[1] = 2;
f[2] = 4;
for (int i = 3; i <= n; i++) {
    f[i] = f[i-1]+f[i-2];
}
cout << f[n]; // vastaus tapauksessa n

Laskeminen modulossa

Usein dynaamisessa ohjelmoinnissa vastaus voi olla suuri eikä mahdu int- tai long-tyyppiin. Tällöin tehtävässä voi olla maininta, että vastaus riittää laskea "modulo $M$", jossa $M$ on jokin luku, eli vastauksen jakojäännös $M$:llä.

Vastauksen voi laskea modulossa toteuttamalla koodi muuten samalla tavalla kuin ennenkin, mutta jokaisessa laskutoimituksessa mukana on modulo. Esimerkiksi yllä olevaa koodia riittäisi muuttaa näin:

f[1] = 2;
f[2] = 4;
for (int i = 3; i <= n; i++) {
    f[i] = (f[i-1]+f[i-2])%M;
}
cout << f[n]; // vastaus tapauksessa n

Huomaa, että jos laskennan aikana on vähennyslasku, tuloksena oleva modulo voi olla negatiivinen, mikä ei ole toivottavaa. Tämän voi estää lisäämällä lukuun $M$, jos se on pienempi kuin $0$:

int x = (a-b)%M;
if (x < 0) x += M;

Ruudukon käsittely

Toinen tavallinen dynaamisen ohjelmoinnin käyttökohde on, että haluamme laskea jotain ruudukkoon liittyvää. Tällöin voimme koettaa muotoilla tehtävän funktiona $f(y,x)$, missä $(y,x)$ on ruudukon kohta. Voimme käyttää dynaamista ohjelmointia, jos tapauksen $(y,x)$ ratkaisun saa laskettua tapauksista $(y',x')$, missä $y' \le y$ ja $x' \le x$.

Yksi tyypillinen tilanne on, että haluamme laskea reittejä, jotka lähtevät ruudukon vasemmasta yläkulmasta ja joissa saa kulkea vain askelia oikealle ja alaspäin. Jälkimmäisen ehdon ansiosta voimme käyttää dynaamista ohjelmointia, koska reitillä olevilla ruuduilla on selkeä järjestys.

Esimerkiksi jos ruudussa $(y,x)$ on luku $a(y,x)$, voimme laskea rekursiolla $$f(y,x)=a(y,x)+\max(f(y-1,x),f(y,x-1)),$$ mikä on suurin lukujen summa reitillä, joka alkaa vasemmasta yläkulmasta ja päättyy kohtaan $(y,x)$. Ideana on valita vasemmalta tai ylhäältä tuleva reitti niin, että summa on mahdollisimman suuri.

Voimme laskea funktion $f(y,x)$ arvot kaikkiin kohtiin seuraavasti:

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        f[i][j] = a[i][j]+max(f[i-1][j],f[i][j-1]);
    }
}

Huomaa, että taulukko on tarkoituksella $1$-indeksoitu, koska silloin reunoilla ruudukon ulkopuolella olevissa kohdissa on oletuksena arvo $0$.