Programowanie dynamiczne może być zmorą większości inżynierów oprogramowania. Nie sądzę, aby istniał jakikolwiek temat, na który otrzymałem więcej pytań.
I całkowicie to rozumiem.
Wywiadowcy uwielbiają zadawać te pytania, ponieważ są one trudne.
Wywiadowcy naprawdę walczą, ponieważ nie mają ram rozwiązywania problemów, aby podejść do problemów DP.
To oznacza, że za każdym razem, gdy próbujesz rozwiązać problem programowania dynamicznego, zaczynasz od początku. Nie możesz zastosować wzorców, które widziałeś z innymi problemami DP, ponieważ wyglądają one zupełnie inaczej. Więc zawsze zaczynasz od nowa i próbujesz rozwiązać te trudne problemy od zera.
W tym poście chcę ci pokazać lepszy sposób.
Następujące filmy przeprowadzą cię przez 6 najczęstszych problemów DP, które możesz spodziewać się zobaczyć w swoich wywiadach. Jeśli nauczysz się tych problemów i dowiesz się, jak zastosować metodę FAST, będziesz w bardzo dobrej formie, aby zmierzyć się z programowaniem dynamicznym w rozmowach kwalifikacyjnych.
Protip: Jeśli jesteś wciąż nowy w programowaniu dynamicznym, sprawdź nasz darmowy 42-stronicowy ebook, Programowanie dynamiczne dla rozmów kwalifikacyjnych, najpierw
Sprawdź problemy:
Najmniejsza zmiana
Dając wejściową ilość reszty x, napisz funkcję, aby określić minimalną liczbę monet potrzebnych do zrobienia tej ilości reszty.
eg. (używając monet amerykańskich)
|
1
2
3
4
|
. change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Longest Common Substring
Given two strings, napisz funkcję, która zwraca najdłuższy wspólny podłańcuch.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Liczba Fibonacciego
Dając liczbę całkowitą n, napisz funkcję obliczającą n-tą liczbę Fibonacciego.
eg.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Podtablica kwadratowa
Dając dwuwymiarową tablicę 1s i 0s, znajdź największą podtablicę kwadratową wszystkich 1s.
eg.
|
1
2
3
|
subarray(
) = 2
|
Iloczyn macierzowy
Dając macierz, znajdź ścieżkę od lewego górnego rogu do prawego dolnego rogu o największym iloczynie, poruszając się tylko w dół i w prawo.
eg.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
1 -> 4 -> 7 -> 8 -> 9
2016
-1 -> 4 -> 5 -> -6 -> 9
1080
|
0-1 Knapsack
Dając listę elementów z wartościami i wagami, a także wagę max, znajdź maksymalną wartość jaką można wygenerować z elementów, gdzie suma wag jest mniejsza od max.
eg.
|
1
2
3
|
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
maxWeight = 5
knapsack(items, maxWeight) = 22
|
.