Viikon 7 aiheena on dynaaminen ohjelmointi ja välikyselyt. Suurimmassa osassa tehtävistä pitää käyttää segmenttipuuta tai summataulukkoa nopeuttamaan dynaamisen ohjelmoinnin laskemista.

Vihjeitä:

Unirytmi

[hint]Käytä dp tilaa dp[k] = tapojen määrä joilla Uolevi voi nukkua k minuuttia. Nopeuta dp:n laskemista summataulukon avulla.[/hint]

Projektit

[hint]Käytä dp tilaa dp[k] = kuinka paljon voi tienata k:n ensimmäisen päivän aikana. Käytä koordinaattikompressiota.[/hint]

Peli

[hint]Käytä dp tilaa dp[k] = kuinka paljon kolikkoja Uolevi voi kerätä jos hän lopettaa kolikkoon k. Käytä maksimisegmenttipuuta nopeampaan dp arvojen laskemiseen[/hint]

Junat

[hint]Käytä dynaamista ohjelmointia. Aina kannattaa valita seuraavaksi asemaksi se josta pääsee pisimmälle.[/hint]

Taulukko

[hint]Keksi segmenttipuurakenne, josta voi kysyä suurinta yhtenäisen alueen summaa.[/hint]