Programowanie dynamiczne to metoda stosowana w matematyce i informatyce do rozwiązywania złożonych problemów poprzez rozbicie ich na prostsze podproblemy. Rozwiązując każdy podproblem tylko raz i przechowując wyniki, pozwala uniknąć zbędnych obliczeń, co prowadzi do bardziej wydajnych rozwiązań szerokiego zakresu problemów. W tym artykule szczegółowo omówiono koncepcje programowania dynamicznego, zilustrowane przykładami.

sprawdzenie Java ma wartość null

Programowanie dynamiczne

Spis treści

• Co to jest programowanie dynamiczne?
• Jak działa programowanie dynamiczne?
• Przykłady programowania dynamicznego
• Kiedy stosować programowanie dynamiczne?
• Podejścia do programowania dynamicznego
• Algorytm programowania dynamicznego
• Zalety programowania dynamicznego
• Zastosowania programowania dynamicznego
• Naucz się podstaw programowania dynamicznego
• Zaawansowane koncepcje w programowaniu dynamicznym
• Problemy programowania dynamicznego

Co to jest programowanie dynamiczne (DP)?

Programowanie dynamiczne (DP) to metoda stosowana w matematyce i informatyce do rozwiązywania złożonych problemów poprzez rozbicie ich na prostsze podproblemy. Rozwiązując każdy podproblem tylko raz i przechowując wyniki, pozwala uniknąć zbędnych obliczeń, co prowadzi do bardziej wydajnych rozwiązań szerokiego zakresu problemów.

Jak działa programowanie dynamiczne (DP)?

• Zidentyfikuj podproblemy: Podziel główny problem na mniejsze, niezależne podproblemy.
• Rozwiązania sklepowe: Rozwiąż każdy podproblem i zapisz rozwiązanie w tabeli lub tablicy.
• Rozwiązania konstrukcyjne: Skorzystaj z przechowywanych rozwiązań, aby opracować rozwiązanie głównego problemu.
• Unikaj redundancji: Przechowując rozwiązania, DP gwarantuje, że każdy podproblem zostanie rozwiązany tylko raz, co skraca czas obliczeń.

Przykłady programowania dynamicznego (DP)

Przykład 1: Rozważmy problem znalezienia ciągu Fibonacciego:

Ciąg Fibonacciego: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Podejście brutalnej siły:

Aby znaleźć n-tą liczbę Fibonacciego za pomocą metody brute-force, wystarczy dodać (n-1)-ty I (n-2)th Liczby Fibonacciego. To by zadziałało, ale byłoby nieefektywne w przypadku dużych wartości N , ponieważ wymagałoby to obliczenia wszystkich poprzednich liczb Fibonacciego.

Podejście do programowania dynamicznego:

Szereg Fibonacciego wykorzystujący programowanie dynamiczne

• Podproblemy: F(0), F(1), F(2), F(3), …
• Rozwiązania sklepowe: Utwórz tabelę do przechowywania wartości F(n) podczas ich obliczania.
• Rozwiązania konstrukcyjne: W przypadku F(n) wyszukaj w tabeli F(n-1) i F(n-2) i dodaj je.
• Unikaj redundancji: Tabela gwarantuje, że każdy podproblem (np. F(2)) zostanie rozwiązany tylko raz.

Używając DP, możemy efektywnie obliczyć ciąg Fibonacciego bez konieczności ponownego obliczania podproblemów.

przycinanie alfa-beta

Przykład 2: Najdłuższy wspólny podciąg (znalezienie najdłuższego podciągu, który jest wspólny dla dwóch ciągów)

Przykład 3: Najkrótsza ścieżka na grafie (znalezienie najkrótszej ścieżki między dwoma węzłami na grafie)

Przykład 4: Problem plecakowy (znalezienie maksymalnej wartości przedmiotów, które można zmieścić w plecaku o danej pojemności)

Kiedy stosować programowanie dynamiczne (DP)?

Programowanie dynamiczne to technika optymalizacji stosowana przy rozwiązywaniu problemów, na którą składają się następujące cechy:

1. Optymalna podbudowa:

Optymalna podstruktura oznacza, że ​​łączymy optymalne wyniki podproblemów, aby osiągnąć optymalny wynik większego problemu.

oprogramowanie systemowe

Przykład:

Rozważmy problem znalezienia minimalny koszt ścieżka na wykresie ważonym z a źródło węzeł do a miejsce docelowe węzeł. Możemy podzielić ten problem na mniejsze podproblemy:

• Znaleźć minimum koszt ścieżka od źródło węzeł do każdego mediator węzeł.
• Znaleźć minimum koszt ścieżkę od każdego mediator węzeł do miejsce docelowe węzeł.

Rozwiązanie większego problemu (znalezienie ścieżki minimalnego kosztu od węzła źródłowego do węzła docelowego) można zbudować na podstawie rozwiązań tych mniejszych podproblemów.

2. Nakładające się podproblemy:

Te same podproblemy są rozwiązywane wielokrotnie w różnych częściach problemu.

Przykład:

Rozważmy problem obliczenia Szereg Fibonacciego . Aby obliczyć liczbę Fibonacciego w indeksie N , musimy obliczyć liczby Fibonacciego w indeksach n-1 I n-2 . Oznacza to, że podproblem obliczenia liczby Fibonacciego w indeksie n-1 jest użyte dwukrotnie w rozwiązaniu większego problemu obliczania liczby Fibonacciego w indeksie N .

Podejścia do programowania dynamicznego (DP)

Programowanie dynamiczne można osiągnąć, stosując dwa podejścia:

1. Podejście odgórne (zapamiętywanie):

W podejściu odgórnym, znanym również jako zapamiętywanie , zaczynamy od rozwiązania końcowego i rekurencyjnie dzielimy je na mniejsze podproblemy. Aby uniknąć zbędnych obliczeń, wyniki rozwiązanych podproblemów przechowujemy w tabeli zapamiętywania.

Rozłóżmy podejście odgórne:

• Rozpoczyna się od rozwiązania końcowego i rekurencyjnie dzieli je na mniejsze podproblemy.
• Przechowuje rozwiązania podproblemów w tabeli, aby uniknąć zbędnych obliczeń.
• Odpowiednie, gdy liczba podproblemów jest duża i wiele z nich jest ponownie wykorzystywanych.

2. Podejście oddolne (tabela):

W podejściu oddolnym, znanym również jako tabulacja , zaczynamy od najmniejszych podproblemów i stopniowo zmierzamy do ostatecznego rozwiązania. Wyniki rozwiązanych podproblemów przechowujemy w tabeli, aby uniknąć zbędnych obliczeń.

Rozłóżmy podejście oddolne:

• Zaczyna się od najmniejszych podproblemów i stopniowo prowadzi do ostatecznego rozwiązania.
• Wypełnia tabelę rozwiązaniami podproblemów w sposób oddolny.
• Odpowiednie, gdy liczba podproblemów jest mała, a optymalne rozwiązanie można obliczyć bezpośrednio z rozwiązań mniejszych podproblemów.

Programowanie dynamiczne (DP) Algorytm

Programowanie dynamiczne to technika algorytmiczna, która rozwiązuje złożone problemy, dzieląc je na mniejsze podproblemy i przechowując ich rozwiązania do wykorzystania w przyszłości. Jest szczególnie skuteczny w przypadku problemów, które zawiera nakładające się podproblemy I optymalna podbudowa.

Typowe algorytmy wykorzystujące programowanie dynamiczne:

• Najdłuższy wspólny podciąg (LCS): Znajduje najdłuższy wspólny podciąg między dwoma ciągami znaków.
• Najkrótsza ścieżka na grafie: Znajduje najkrótszą ścieżkę między dwoma węzłami na wykresie.
• Problem z plecakiem: Określa maksymalną wartość przedmiotów, które można umieścić w plecaku o danej pojemności.
• Mnożenie łańcucha macierzy: Optymalizuje kolejność mnożenia macierzy, aby zminimalizować liczbę operacji.
• Ciąg Fibonacciego: Oblicza n-tą liczbę Fibonacciego.

Zalety programowania dynamicznego (DP)

Programowanie dynamiczne ma wiele zalet, w tym:

• Pozwala uniknąć wielokrotnego obliczania tych samych podproblemów, co prowadzi do znacznych oszczędności czasu.
• Zapewnia znalezienie optymalnego rozwiązania poprzez rozważenie wszystkich możliwych kombinacji.
• Dzieli złożone problemy na mniejsze, łatwiejsze do rozwiązania podproblemy.

Zastosowania programowania dynamicznego (DP)

Programowanie dynamiczne ma szeroki zakres zastosowań, w tym:

• Optymalizacja: Problem plecakowy, problem najkrótszej ścieżki, problem maksymalnej podtablicy
• Informatyka: Najdłuższy wspólny podciąg, odległość edycji, dopasowanie ciągów
• Badania operacyjne: Zarządzanie zapasami, planowanie, alokacja zasobów

Przyjrzyjmy się teraz kompleksowemu planowi działania prowadzącemu do opanowania programowania dynamicznego.

czas trwania Javy

Naucz się podstaw programowania dynamicznego (DP)

• Co to jest zapamiętywanie? Kompletny samouczek
• Tabulacja a zapamiętywanie
• Optymalna właściwość podbudowy
• Właściwość nakładających się podproblemów
• Jak rozwiązać problem programowania dynamicznego?

• Liczby Fibonacciego
• n-ty numer kataloński
• Numery dzwonków (liczba sposobów podziału zestawu)
• Współczynnik dwumianowy
• Problem ze zmianą monety
• Problem z sumą podzbiorów
• Oblicz nCr % p
• Cięcie pręta
• Algorytm malowania ogrodzenia
• Najdłuższy wspólny podciąg
• Najdłuższy podciąg rosnący
• Najdłuższy podciąg taki, że różnica między sąsiednimi wynosi jeden
• Podmacierz kwadratowa o maksymalnym rozmiarze ze wszystkimi jedynekami
• Ścieżka kosztu minimalnego
• Minimalna liczba skoków do osiągnięcia końca
• Najdłuższy wspólny podciąg (rozwiązanie DP zoptymalizowane pod kątem przestrzeni)
• Policz sposoby dotarcia do n-tego stopnia, wykonując krok 1, 2 lub 3
• Policz wszystkie możliwe ścieżki od lewego górnego rogu do prawego dolnego rogu macierzy mXn
• Unikalne ścieżki w siatce z przeszkodami

2. Średnie problemy z programowaniem dynamicznym (DP)

• Algorytm Floyda Warshalla
• Algorytm Bellmana-Forda
• 0-1 Problem z plecakiem
• Drukowanie przedmiotów w plecaku 0/1
• Nieograniczony plecak (dozwolone powtarzanie przedmiotów)
• Puzzle z upuszczaniem jajek
• Problem z łamaniem wyrazów
• Problem z pokryciem wierzchołków
• Problem z układaniem płytek
• Problem z układaniem pudełek
• Problem z partycją
• Problem komiwojażera | Zestaw 1 (programowanie naiwne i dynamiczne)
• Najdłuższy podciąg palindromiczny
• Najdłuższy wspólny podciąg rosnący (LCS + LIS)
• Znajdź wszystkie odrębne sumy podzbiorów (lub podciągów) tablicy
• Ważone planowanie pracy
• Policz zaburzenia (permutacja taka, że ​​żaden element nie pojawia się na swoim pierwotnym miejscu)
• Minimalne wstawki, aby utworzyć palindrom
• Dopasowanie wzorca wieloznacznego
• Sposoby układania piłek w taki sposób, aby sąsiednie kule były różnych typów

3. Trudne problemy w programowaniu dynamicznym (DP)

• Podział palindromu
• Problem z zawijaniem słów
• Problem podziału malarza
• Program do rozwiązywania problemów z mostkiem i pochodnią
• Mnożenie łańcucha macierzy
• Drukowanie nawiasów w problemie mnożenia łańcucha macierzy
• Maksymalna suma prostokątów w macierzy 2D
• Maksymalny zysk przy zakupie i sprzedaży akcji najwyżej k razy
• Minimalny koszt sortowania ciągów przy użyciu operacji odwracania o różnych kosztach
• Liczba podciągów AP (postępu arytmetycznego) w tablicy
• Wprowadzenie do programowania dynamicznego na drzewach
• Maksymalna wysokość drzewa, gdy dowolny węzeł można uznać za korzeń
• Najdłuższy powtarzający się i nienakładający się podciąg

Szybkie linki:

• Naucz się struktury danych i algorytmów | Poradnik DSA
• 20 najważniejszych pytań do rozmowy kwalifikacyjnej na temat programowania dynamicznego
• „Zadania praktyczne” dotyczące programowania dynamicznego
• „Quiz” na temat programowania dynamicznego