Megoldás
Két függvényt vezetünk, be.
Ráépítési költségek
$g(i,j)$ = annak a költsége aranyban, ha az i.-től a j.-dik lépcsőkig
csinálunk egy ráépítést, tehát az i.-től a j.-ig fokig egyetlen lépcsőfokká vonjuk össze
a fokokat. ($1\le i \le j \le {\mathtt L}$ és $g(i,i)=0$)
Optimális részmegoldások
$f_{\mathtt A}({\mathtt L})$ = annak a minimális költsége aranyban, hogy az első L lépcsőt A-ra építjük át. ($1\le {\mathtt A} \lt {\mathtt L}$)
Rekurzió
Vegyük észre, hogy $f_1(j) = g(1,j)$. Az utolsó lépcsőfok szerint ágazunk el:
$f_{\mathtt A}({\mathtt L})=\min_{A\le i \le L}\left\{g(i,{\mathtt L})+f_{{\mathtt A}-1}(i-1) \right\}$
Optimalizálás: dinamikus programozás :)
Látható, hogy az $f$ függvényt mindig kisebb értékekkel hívjuk a
minimum kiszámításánál, tehát értékeit táblázatolva $A\cdot L$ lépésszámú
algoritmust nyerünk.
Kód
