Algorytmy i struktury danych · Middle · Pytanie 40 z 75
Które dwie własności sprawiają, że problem pasuje do programowania dynamicznego?
- 1Posortowane dane i jedna unikalna odpowiedź
- ✓Poprawna odpowiedź: Nakładające się podproblemy i optymalna podstruktura
- 3Struktura grafu z dodatnimi wagami krawędzi
Wyjaśnienie
Podproblemy się nakładają, gdy te same wyniki pośrednie są potrzebne wiele razy, więc opłaca się je zapamiętać. Optymalna podstruktura oznacza, że najlepsza odpowiedź składa się z najlepszych odpowiedzi na podproblemy.