Tällä viikolla aloitamme tutustumisen dynaamiseen ohjelmointiin. KKKK:n luvut 21–23 auttavat tehtävissä.

Lukiolaisten Datatähti-kisa käytiin to 29.1. alustana CSES. Jos haluat katsoa kisan tehtäviä, paina tästä. Voit myös kokeilla lähettää omia ratkaisujasi tehtäviin (ne eivät vaikuta tulostauluun, koska kisa on jo ohi).

Vinkit

Kilpailu

[hint]Muodosta rekursiivinen funktio T(k, x), joka on eri tapojen lukumäärä muodostaa summa x tehtävistä 1\ldots k. Käytä dynaamista ohjelmointia vastauksien selvittämiseen T-funktiolla.[/hint]

Lukujono

[hint]Huomaa, että vain osaa arvoista U_0, U_1, U_2, \ldots, U_{n-1} tarvitaan arvon U_n laskemiseen.[/hint]

Ruudukko

[hint]Laske jokaiseen ruudukon ruutuun aakkosjärjestyksessä pienin siihen päättyvä merkkijono.[/hint]

Unirytmi

[hint]Käytä summataulukkoa nopeuttamaan dynaamista ohjelmointia.[/hint]

Taulukko

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