Dvojrozmerná dynamika

Doposiaľ sme používali len jednorozmerné polia na riešenie úloh, ktoré vyžadovali iba jeden stav -- napr. aktuálny index alebo hodnota.

Niektoré úlohy však vyžadujú rozhodovanie na základe dvoch stavových premenných. V takých prípadoch potrebujeme dynamické programovanie s dvojrozmernými tabuľkami.

Typickými prákladmi sú:

• porovnávanie sekvencií,
• úlohy na výber položiek,
• pohyb v 2D mriežke.

V dvojrozmernom dynamickom programovaní budeme teda používať dvojrozmernú tabuľku, kde každá bunka bude obsahovať optimálne riešenie pre konkrétnu kombináciu týchto dvoch stavových premenných.

Podobne ako pri jednorozumernom dynamickom programovaní, aj tu budeme riešenie skladať po častiach z menších podproblémov. Rozdiel je v tom, že teraz sa budeme pohybovať v tabuľke miesto jednorozmerného poľa.

Jednoduchý príklad

Nachádzame sa v ľavom hornom rohu štvorčekovej siete veľkosti $m \times n$. Môžeme sa hýbať iba doprava alebo nadol. Koľkými spôsobmi sa môžeme dostať do pravého dolného rohu tejto siete?

Podobne ako pri jednorozmernej dynamike začneme tým, že si zadefinujeme menší podproblém, ktorý reprezentuje menšiu časť pôvodného problému.

Predstavme si, že stojíme na políčku $(x,y)$. Koľkými spôsobmi sme sa naň mohli dostať? Prišli sme sem buď zľava, alebo zhora. Ak vieme, koľkými spôsobmi sme sa dostali na tieto predchádzajúce políčka, počet spôsobov, ako sa vieme dostať na $(x,y)$ bude ich súčtom.

Hodnota $D[x][y]$ bude uvádzať, koľkými spôsobmi sa vieme dostať na políčko $(x,y)$. Ako sme už načrtli vyššie:

• ak prichádzame zľava, ide o $D[x-1][y]$ možností,
• ak prichádzame zhora, ide o $D[x][y-1]$ možností.

Teda platí: $D[x][y] = D[x-1][y] + D[x][y-1]$.

Ak je políčko v prvom riadku alebo prvom stĺpci, nemôžeme brať do úvahy políčka mimo hraníc tabuľky. Jedinou výnimkou je počiatočné políčko $(0,0)$, na ktoré vedie práve jeden spôsob -- začíname na ňom.

Ak budeme tabuľku $D[x][y]$ vypĺňať v rozumnom poradí (zľava doprava, zhora nadol), vždy budeme mať už vypočítané potrebné hodnoty. Tak môžme jednoducho využiť náš vyššie odvodený vzťah.