1. Nyers erő és rekurzió
Egy rekurzív függvénnyel adunk maximumot, aminek kér paramétere
egy prefix (az eddig meghagyott kövek), és egy index (melyik kőről döntünk most).
A prefix $2^m$-féle lehet, ez exponenciális algoritmus, de kb. m=30-ig
használható.
opt(prefix, i):
Ha i > m akkor vissza(m-hossz(prefix)) Elágazás vége
c := stones[i]
Ha (c nem_eleme(prefix)) vagy (c=utolsó_karakter(prefix))
akkor opt1 := opt(prefix+c,i+1)
különben opt1 := végtelen
Elágazás vége
opt2 := opt(prefix,i+1)
vissza( min(opt1,opt2) )
függvény vége
A megoldás pedig:
minimum := opt('',1)
2. Optimalizálás: paraméter-tér transzformáció és DP
Ahhoz, hogy dinamikus programozásra írjuk át a rekurziót, csökkenteni kell a
paraméterel lehetséges számát.
Vegyük észre, hogy a prefixből csak az utolsó karakterét és az eddigi karakterek
halmazát használjuk. Tehát a prefix helyett elegendő az utolsó karaktert, az eddigi karakter-halmazt és a prefix hosszát megadni.
Ez legfeljebb
$5\cdot 32\cdot 100$ lehetőség. Ezek és az opt() "i" bemenete lesznek a DP tömbjének indexei.
cache[utolsó][halmaz][hossz][ind]
A DP-s változat:
opt(utolsó,halmaz,hossz, i):
Ha cache[utolsó][halmaz][hossz][i] != -1
akkor
vissza( cache[utolsó][halmaz][hossz][i] )
különben
Ha i > m
akkor válasz := (m-hossz)
különben
c := stones[i]
Ha (c nem_eleme(halmaz)) vagy (c=utolsó)
akkor opt1 := opt(c,halmaz+c,hossz+1,i+1)
különben opt1 := végtelen
Elágazás vége
opt2 := opt(utolsó,halmaz,hossz,i+1)
válasz := min(opt1,opt2)
Elágazás vége
cache[utolsó][halmaz][hossz][i] := válasz
vissza( válasz)
Elágazás vége
függvény vége
Kódok
