Przegląd kluczowych pojęć
Lekcja 14 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.
W tej lekcji powtórzymy kluczowe pojęcia omówione w kursie Dynamic Programming 101.
- Programowanie dynamiczne: Programowanie dynamiczne to technika rozwiązywania problemów optymalizacyjnych poprzez rozbijanie ich na prostsze podproblemy i rozwiązywanie każdego podproblemu tylko raz.
- Memoizacja: Memoizacja to technika pozwalająca uniknąć zbędnych obliczeń poprzez przechowywanie wyników kosztownych wywołań funkcji i zwracanie wyniku z pamięci podręcznej, gdy ponownie wystąpią te same dane wejściowe.
- Tabulacja: Tabulacja to technika rozwiązywania problemów programowania dynamicznego polegająca na iteracyjnym wypełnianiu tabeli lub tablicy rozwiązań, aż do uzyskania końcowego rozwiązania.
- Optymalna podstruktura: Problem ma optymalną podstrukturę, jeśli jego optymalne rozwiązanie zawiera w sobie optymalne rozwiązania jego podproblemów.
- Nakładające się podproblemy: Problem ma nakładające się podproblemy, jeśli można go rozbić na podproblemy, które mają wspólne podpodproblemy.
- Optymalizacja pamięci: Optymalizacja pamięci to technika ograniczania wymagań dotyczących pamięci algorytmu programowania dynamicznego poprzez śledzenie tylko niezbędnego stanu.
- Maskowanie bitów: Maskowanie bitów to technika wykorzystująca operacje bitowe do reprezentowania zbioru elementów jako liczby binarnej.
- Przycinanie: Przycinanie to technika ograniczania liczby obliczeń wymaganych przez algorytm programowania dynamicznego poprzez unikanie niepotrzebnych obliczeń.
Wyzwanie
ŚredniWyzwanie podsumowujące: ścieżka o minimalnym koszcie
Dany jest grid n x n przedstawiający mapę miasta. Każda komórka w gridzie reprezentuje skrzyżowanie ulic, a wartości w komórkach oznaczają koszt przejazdu przez dane skrzyżowanie. Chcesz przemieścić się z lewego górnego rogu gridu do prawego dolnego rogu i na każdym skrzyżowaniu możesz poruszać się tylko w dół lub w prawo.
Napisz funkcję min_cost_path(grid), która przyjmuje grid jako dane wejściowe i zwraca minimalny koszt przejazdu przez grid z lewego górnego do prawego dolnego rogu.
Na przykład:
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
min_cost_path(grid) => 7Wyjaśnienie: Ścieżka o minimalnym koszcie to 1 -> 3 -> 1 -> 1 -> 1, a jej całkowity koszt wynosi 7.
Spróbuj swoich sił
def min_cost_path(grid):
# Napisz kod tutajWszystkie lekcje w sekcji Programowanie dynamiczne — podstawy
1Wprowadzenie do programowania dynamicznego
Czym jest programowanie dynamiczne?Dlaczego jest ważne?Zastosowania w różnych dziedzinach4Zaawansowane zagadnienia
Minimalna długość podtablicyPrzycinanieOptymalizacja pamięciMaskowanie bitów3Algorytmy programowania dynamicznego
Najdłuższy wspólny podciągProblem plecakowyProblem wydawania resztyOdległość edycyjnaPoćwicz samodzielnie: Kompilator Python online