Geriausio sprendinio iš aibės galimų sprendinių nustatymas yra sudėtingas, bet labai naudingas. Šiuo atveju renkant saldainius galimi 70 skirtingų būdų, kaip iš A langelio nueiti į B langelį. Tai puiki Paskalio trikampio taikymo versija. Šiuo atveju surenkami geriausi daliniai rezultatai, atmetant kitus. Kadangi langelių palyginti nedaug, atmesti blogus variantus nėra labai sudėtinga paprastai skaičiuojant ir analizuojant. Efektyvesnis sprendimas, kai lentelei pildyti taikomas dinaminio programavimo metodas. Šio uždavinio algoritmas skirtas kiekvieno langelio didžiausiam saldainių skaičiui nustatyti, todėl užtenka 25 skaičiavimų ir nebereikia kartoti tų pačių veiksmų.

http://www.radford.edu/~nokie/classes/360/dp-memoized.html

Raktiniai žodžiai: algoritmas, komanda robotui.

Teisingas atsakymas yra 14.

Galimas sprendimas – užpildyti visus lentelės langelius didžiausiais saldainių, kurie gali būti surinkti robotui atėjus į langelį, skaičiais. Pradedame A langelyje – jame nėra saldainių.

Toliau renkant saldainius gretimuose pirmajam langeliuose, įrašomas galimas didžiausias surinktų saldainių skaičius.

Toliau skaičiuojant saldainius ir ieškant didžiausio galimų surinkti atėjus į tam tikrą langelį saldainių skaičiaus, galima sudaryti tokį algoritmą: skaičiuojant bet kurio langelio didžiausią saldainių skaičių, reikia prie to langelio skaičiaus pridėti didžiausią iš kairėje ar apačioje esančių skaičių. Matematiškai tai galima užrašyti masyvo elementais:

v(i, 0) = 0

v(0, j) = 0

v(i, j) = c(i, j) + max{v(i – 1, j), v(i, j – 1)},

čia v(i, j) yra didžiausias saldainių, kuriuos galima surinkti einant į (i, j) langelį, skaičius, o c(i, j) – saldainių, esančių pačiame langelyje, skaičius.

Kadangi skaičiuodami saldainius turime žiūrėti į skaičius, įrašytus langelio kairėje ir apačioje esančiuose langeliuose, tai prasminga lentelę papildyti stulpeliu iš kairės ir eilute iš apačios. Užpildyta lentelė atrodo taip: