Viikon 4 aiheena on dynaaminen ohjelmointi. KKKK luvussa 7 kerrotaan siitä.

Joissain tehtävissä vastaus on hyvin suuri, joten se pitää ilmoittaa modulo joku alkuluku. Jos laskeminen modulossa ei ole tuttua, voit katsoa esim. https://en.wikipedia.org/wiki/Modulo_operation ja KKKK sivuilla 6-7 olevan osion "Vastaus modulossa".

Alla on vihjeitä tehtäviin. Kannattaa kuitenkin ensin miettiä ilman vihjettä. Vihjeen näet maalaamalla sen hiirellä.

Uusi aita

[hint]Käytä dynaamisen ohjelmoinnin tilana funktiota dp[n][k] joka kertoo kuinka monella tavalla n ensimmäistä laudan pituutta voidaan valita niin että n:nnen laudan pituus on k[/hint]

Outo DNA

[hint]Tallenna jokaisen merkin määrän parillisuus[/hint]

Salasana

[hint]Tallenna kuinka pitkälle ollaan päästy jääkiekkojoukkueen nimen muodostamisessa[/hint]

[hint]Tehtävän voi ajatella myös äärellisten automaattien kautta. (ks. Laskennan mallit kurssi). Muodosta automaatti joka tunnistaa merkkijonot joissa esiintyy jossain kohtaa jääkiekkojoukkueen nimi.[/hint]

Merkkijono

[hint]Tehtävä kannattaa ajatella niin että pitää yhdistää merkkijonon osat joiden pituudet annetaan[/hint]

[hint]Käytä tilaa dp[l][r], kuinka paljon maksaa yhdistää osat l...r. Tarkoitetun ratkaisun aikavaativuus on O(m^3)[/hint]

Peli

[hint]Mieti pelin kulkua lopusta alkuun.[/hint]

Bonustehtävä: Merkkijono

[hint]Käytä samoja dp tiloja mutta löydä optimaalinen valinta nopeammin[/hint]