Rozkopané křižovatky (Úlohy z MO kategorie P, 42. část) - Töpfer, Pavel (Matematika–Fyzika–Informatika, 2021)
V dalším dílu cyklu zajímavých úloh z Matematické olympiády kategorie P (programování) se seznámíme s jednou praktickou úlohou z celostátního kola 45. ročníku MO (školní rok 1995/96). Úkolem v ní bylo určit počet různých cest mezi dvěma body v pravidelné pravoúhlé silniční síti, ve které jsou ovšem některé křižovatky neprůjezdné. K efektivnímu vyřešení této úlohy použijeme poměrně známou programátorskou techniku dynamického programování. Ukážeme si různé způsoby, jak lze takové řešení implementovat, a také skutečnost, že se tyto způsoby mohou lišit z hlediska výsledné časové složitosti. Stejné principy ovšem platí i pro řešení mnoha jiných úloh využívajících dynamické programování.