Programowanie dynamiczne: przykłady, typowe problemy i rozwiązania

Nie ma wątpliwości, że problemy z programowaniem dynamicznym mogą być bardzo onieśmielające podczas wywiadu z kodowaniem. Nawet jeśli wiesz, że problem wymaga rozwiązania za pomocą metody programowania dynamicznego, znalezienie działającego rozwiązania w ograniczonym czasie jest wyzwaniem.

Najlepszym sposobem, aby być dobrym w rozwiązywaniu problemów związanych z programowaniem dynamicznym, jest rozwiązywanie ich jak największej liczby. Chociaż nie musisz koniecznie zapamiętywać rozwiązania każdego problemu, dobrze jest mieć pomysł, jak go wdrożyć.

Co to jest programowanie dynamiczne?

Mówiąc najprościej, programowanie dynamiczne jest metodą optymalizacji algorytmów rekurencyjnych, z których większość jest używana do rozwiązywania problemów obliczeniowych lub matematycznych.

Można to również nazwać techniką algorytmiczną do rozwiązywania problemu optymalizacji, dzieląc go na prostsze podproblemy. Kluczową zasadą, na której opiera się programowanie dynamiczne, jest to, że optymalne rozwiązanie problemu zależy od rozwiązań jego podproblemów.

Wszędzie tam, gdzie widzimy rozwiązanie rekurencyjne, które wielokrotnie wywoływało te same dane wejściowe, możemy je zoptymalizować za pomocą programowania dynamicznego. Chodzi o to, aby po prostu przechowywać wyniki podproblemów, abyśmy nie musieli ich ponownie obliczać, gdy zajdzie taka potrzeba.

Dynamicznie programowane rozwiązania mają wielomianową złożoność, która zapewnia znacznie krótszy czas działania niż inne techniki, takie jak rekurencja lub cofanie. W większości przypadków programowanie dynamiczne zmniejsza złożoność czasową, znaną również jako duże-O, od wykładniczej do wielomianu.

Co to jest notacja Big-O?

Twój kod musi być wydajny, ale jak pokazać, jak wydajne jest coś? Z Big-O!

Teraz, gdy już wiesz, czym jest programowanie dynamiczne, czas sprawdzić kilka typowych problemów i ich rozwiązania.

Dynamiczne problemy z programowaniem

1. Problem z plecakiem

Stwierdzenie problemu

Mając zestaw elementów, z których każdy ma wagę i wartość, określ liczbę każdego elementu, który ma zostać uwzględniony w pliku zbiórki tak, aby całkowita waga nie przekroczyła określonego limitu, a łączna wartość była równa możliwy.

Otrzymasz dwie tablice liczb całkowitych wartości [0..n-1] i wagi [0..n-1] które reprezentują wartości i wagi związane odpowiednio z n pozycjami. Podana jest również liczba całkowita W. która reprezentuje pojemność plecaka.

Tutaj rozwiązujemy problem plecaka 0/1, co oznacza, że ​​możemy dodać element lub go wykluczyć.

Algorytm

• Utwórz dwuwymiarową tablicę za pomocą n + 1 rzędy i w + 1 kolumny. Numer wiersza n oznacza zbiór pozycji od 1 do jai numer kolumny w oznacza maksymalną nośność torby.
• Wartość liczbowa w [i] [j] oznacza całkowitą wartość pozycji do ja w torbie o maksymalnej wadze j.
• Na każdej współrzędnej [i] [j] w tablicy wybierz maksymalną wartość, którą możemy uzyskać bez pozycja ilub maksymalna wartość, jaką możemy uzyskać pozycja icokolwiek jest większe.
• Maksymalna możliwa do uzyskania wartość poprzez uwzględnienie pozycji i jest sumą pozycji ja i maksymalną wartość, jaką można uzyskać przy pozostałej pojemności plecaka.
• Wykonuj ten krok, aż znajdziesz maksymalną wartość dla W.^th rząd.

Kod

def FindMax (W, n, wartości, wagi):
MaxVals = [[0 for x in range (W + 1)] for x in range (n + 1)]
dla i w zakresie (n + 1):
dla w w zakresie (W + 1):
if i == 0 lub w == 0:
MaxVals [i] [w] = 0
wagi elif [i-1] <= w:
MaxVals [i] [w] = max (wartości [i-1]
+ MaxVals [i-1] [w-weights [i-1]], 
MaxVals [i-1] [w])
jeszcze:
MaxVals [i] [w] = MaxVals [i-1] [w]
return MaxVals [n] [W]

2. Problem ze zmianą monet

Stwierdzenie problemu

Załóżmy, że masz tablicę liczb reprezentujących wartości każdej monety. Biorąc pod uwagę określoną kwotę, znajdź minimalną liczbę monet potrzebną do zrobienia tej kwoty.

Algorytm

• Zainicjuj tablicę o rozmiarze n + 1, gdzie n to kwota. Zainicjuj wartość każdego indeksu ja w tablicy, aby była równa kwocie. Oznacza maksymalną liczbę monet (przy użyciu monet o nominale 1) potrzebną do uzupełnienia tej kwoty.
• Ponieważ nie ma nominału dla 0, zainicjuj przypadek bazowy, gdzie tablica [0] = 0.
• Dla każdego innego indeksu japorównujemy wartość w nim (która jest początkowo ustawiona na n + 1) z wartością tablica [i-k] +1, gdzie k jest mniej niż ja. To zasadniczo sprawdza całą tablicę aż do i-1, aby znaleźć minimalną możliwą liczbę monet, których możemy użyć.
• Jeśli wartość w jakimkolwiek tablica [i-k] + 1 jest mniejsza niż istniejąca wartość w tablica [i], zamień wartość na tablica [i] z tym o godz tablica [i-k] +1.

Kod

def coin_change (d, kwota, k):
liczby = [0] * (kwota + 1)
dla j w zakresie (1, kwota + 1):
minimum = kwota
dla i w zakresie (1, k + 1):
if (j> = d [i]):
minimum = min (minimum, 1 + liczby [j-d [i]])
liczby [j] = minimum
numery zwrotne [kwota]

3. Fibonacci

Stwierdzenie problemu

Seria Fibonacciego to ciąg liczb całkowitych, w którym następna liczba całkowita w szeregu jest sumą dwóch poprzednich.

Jest definiowany przez następującą relację rekurencyjną: F (0) = 0, F (n) = F (n-1) + F (n-2), gdzie F (n) jest n^th semestr. W tym zadaniu musimy wygenerować wszystkie liczby w ciągu Fibonacciego aż do danego n^th semestr.

Algorytm

• Najpierw użyj podejścia rekurencyjnego, aby zaimplementować daną relację powtarzania.
• Rekurencyjne rozwiązanie tego problemu pociąga za sobą załamanie F (n) w F (n-1) + F (n-2), a następnie wywołując funkcję za pomocą F (n – 1) i F (n + 2) jako parametry. Robimy to do momentu, gdy podstawowe przypadki n = 0lub n = 1 są osiągane.
• Teraz używamy techniki zwanej zapamiętywaniem. Przechowuj wyniki wszystkich wywołań funkcji w tablicy. Zapewni to, że dla każdego n F (n) wystarczy obliczyć tylko raz.
• W przypadku kolejnych obliczeń jego wartość można po prostu pobrać z tablicy w stałym czasie.

Kod

def fibonacci (n): 
fibNums = [0, 1] 
dla i w zakresie (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
zwracane numery fib [n] 

4. Najdłuższa narastająca kolejność

Stwierdzenie problemu

Znajdź długość najdłuższego rosnącego podciągu wewnątrz danej tablicy. Najdłuższy rosnący podciąg to podciąg w tablicy liczb o rosnącym porządku. Liczby w podciągu muszą być unikalne i w porządku rosnącym.

Ponadto elementy sekwencji nie muszą następować po sobie.

Algorytm

• Zacznij od podejścia rekurencyjnego, w którym obliczasz wartość najdłuższego rosnącego podciągu każda możliwa podtablica od indeksu zero do indeksu i, gdzie i jest mniejsze lub równe rozmiarowi szyk.
• Aby zmienić tę metodę w metodę dynamiczną, utwórz tablicę do przechowywania wartości dla każdego podciągu. Zainicjuj wszystkie wartości tej tablicy na 0.
• Każdy indeks ja tej tablicy odpowiada długości najdłuższej rosnącej podsekcji dla podtablicy o rozmiarze ja.
• Teraz dla każdego rekurencyjnego wywołania findLIS (arr, n), Sprawdź n^th indeks tablicy. Jeśli ta wartość wynosi 0, oblicz wartość za pomocą metody z pierwszego kroku i zapisz ją w pliku n^th indeks.
• Na koniec zwróć maksymalną wartość z tablicy. Jest to długość najdłuższego narastającego podciągu danego rozmiaru n.

Kod

def findLIS (myArray):
n = len (myArray)
lis = [0] * n
dla i w zakresie (1, n):
dla j w zakresie (0, i):
if myArray [i]> myArray [j] and lis [i] lis [i] = lis [j] +1
maxVal = 0
dla i w zakresie (n):
maxVal = max (maxVal, lis [i])
return maxVal

Rozwiązania problemów z programowaniem dynamicznym

Teraz, gdy rozwiązałeś już niektóre z najpopularniejszych problemów związanych z programowaniem dynamicznym, czas spróbować samodzielnie wdrożyć rozwiązania. Jeśli utkniesz, zawsze możesz wrócić i zapoznać się z sekcją algorytmów dotyczącą każdego z powyższych problemów.

Biorąc pod uwagę, jak popularne są dziś techniki, takie jak rekurencja i programowanie dynamiczne, nie zaszkodzi sprawdzić kilka popularnych platform, na których można nauczyć się takich pojęć i doskonalić swoje umiejętności kodowania. Chociaż możesz nie napotkać tych problemów na co dzień, na pewno napotkasz je podczas wywiadu technicznego.

Oczywiście, posiadanie wiedzy na temat typowych problemów jest z pewnością opłacalne, kiedy idziesz na następną rozmowę kwalifikacyjną. Więc otwórz swój ulubione IDEi zaczynaj!

9 najlepszych kanałów YouTube do nauki programowania

Gotowy do kodowania? Te kanały YouTube to świetny sposób na rozpoczęcie tworzenia gier, aplikacji, stron internetowych i innych.

O autorze