Úlohy na procvičení

Často je snazší nejprve vymyslet rekurzivní řešení a pak ho převézt na dynamické programování (nebo aspoň udělat memoizaci).

Počet cest v DAGu

Mějme orientovaný graf bez cyklů (DAG). V grafu vybereme jeden vrchol jako start a druhý vrchol jako cíl. Určete, kolik existuje různých cest ze startu do cíle.

Příklad

V grafu na následujícím obrázku existuje 5 cest mezi vrcholy 0 a 5.

graph

Nápověda (rekurze)

Pro každý vrchol sečtěte počty cest z jeho následovníků.

Nápověda (DP)

DP provádějte od cíle (využijte topologické uspořádání vrcholů).

Nejdelší rostoucí podposloupnost

Na vstupu máte posloupnost celých čísel. Vyberte z ní nejdelší podposloupnost (nemusí být souvislá), která je rostoucí. Pokud jich existuje více, vraťte libovolnou z nich.

Příklad

Pro posloupnost 2, 7, 5, 8, 14, 20, 20, 26, 15, 16, 17 je řešení 2, 7, 8, 14, 15, 16, 17 (délka 7).

Nápověda (DP)

Jděte postupně od začátku do konce a pro každý prvek si uložte, jak dlouhá je nejdelší rostoucí podposloupnost, která v něm končí.

Editační vzdálenost řetězců

Editační vzdálenost (též (nebo Levenshteinova) dvou řetězců je definovaná jako nejmenší počet povolených znakových operací, které jsou potřeba k převedení jednoho řetězce na druhý.

Povolené znakové operace jsou

  • substituce znaku (nahrazení jednoho znaku jiným znakem),
  • vložení znaku,
  • smazání znaku.

Spočítejte editační vzdálenost dvou zadaných řetězců.

Pokud chcete vaše řešení otestovat, můžete ho odevzdat do ReCodExu.

Příklad

Vstup:

Hello World
Hallo xWorld

Výstup:

2

Operace, které odpovídají dané hodnotě, jsou substituce 2. znaku (e => a) a vložení znaku (x) na pozici 7.

Nápověda (rekurze)

Začněte od prvního znaku. Pokud jsou první znaky obou řetězců stejné, výsledek je editační vzdálenost zbytků obou řetězců. Pokud se první znaky řetězců liší, vyzkoušejte všechny tři možné operace, abyste první znak opravili.

Nápověda (memoizace)

Místo předávání celých zbytků řetězců si předejte jen index, odkud dál chcete řetězce porovnávat. Pak je snadné udělat memoizaci pomocí 2D pole.

Nápověda (DP)

Rozmyslete si, jak jednotlivé operace odpovídají pohybům v 2D poli pro memoizaci. Z toho pak jde určit, jak tabulku vyplňovat pomocí DP.

Lampy na ulici

Řešte úlohu Lampy na ulici ze soutěže Kasiopea.

Nápověda (DP)

Jděte postupně od začátku do konce. Pro každou lampu spočtěte dvě hodnoty: minimální spotřebu úseku od začátku až k dané lampě,

  1. pokud daná lampa svítí,
  2. pokud daná lampa nesvítí.

Učební výstupy

Učební výstupy podávají zhuštěný souhrn základních konceptů a dovedností, které byste měli umět vysvětlit a/nebo použít po každém cvičení.

  • pomocí memoizace (cache) zrychlit výpočet rekurzivních funkcí (neopakovat víckrát stejný výpočet)
  • využít techniku dynamické programování pro odstranění rekurze (vyplňovat cache popořadě pomocí cyklu)