Memoizacja kontra tabulacja
Dwa sposoby buforowania odpowiedzi podproblemów
Memoizacja kontra tabulacja to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Po co w ogóle buforowanie
Rekurencja naiwna wykonuje tę samą pracę wielokrotnie. Programowanie dynamiczne przechowuje każdą odpowiedź raz, dzięki czemu nie trzeba jej ponownie obliczać.
fib(40) # slow: recomputes endlesslyNakładające się podproblemy
DP stosuje się, gdy problem dzieli się na nakładające się podproblemy. Ten sam mniejszy przypadek pojawia się w wielu gałęziach rekurencji.
fib(5) needs fib(3) twicePodejście zstępujące: memoizacja
Memoizacja to zwykła rekurencja połączona z pamięcią podręczną. Obliczenie wykonuje się na żądanie, a wynik zapamiętuje przy pierwszym napotkaniu każdego argumentu.
memo = {}Łatwa memoizacja w Pythonie
Dekorator lru_cache zamienia wolną rekurencję w szybkie DP za pomocą jednej linii, automatycznie buforując każde wywołanie.
from functools import lru_cache
@lru_cache(None)
def f(n): ...Podejście wstępujące: tabulacja
Tabulacja wypełnia tabelę, zaczynając od najmniejszych przypadków i dochodząc do odpowiedzi, przy użyciu pętli zamiast rekurencji.
dp = [0] * (n + 1)Tablicowany ciąg Fibonacciego
Należy ustawić wartości bazowe, a następnie pozwolić każdej komórce odczytać wartości już obliczone. Bez stosu wywołań, za to z prostą pętlą.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Ta sama odpowiedź, inny styl
Memoizacja i tabulacja rozwiązują tę samą rekurencję. Różnią się tylko kierunkiem: od góry na dół na żądanie albo od dołu do góry w ustalonej kolejności.
Kiedy wybrać memoizację
Warto wybrać memoizację, gdy rekurencję można naturalnie zapisać i nie wszystkie stany muszą zostać obliczone.
Kiedy wybrać tabulację
Należy wybrać tabulację dla ciasnych pętli, aby uniknąć błędów limitu rekurencji oraz wtedy, gdy i tak zostanie obliczona cała tabela.
import sys; sys.setrecursionlimit(10**6)Uwaga na limit rekurencji
Głęboka rekurencja z memoizacją może przekroczyć pythonowy limit rekurencji i zakończyć działanie błędem wykonania dla dużych danych wejściowych.
Obie metody mają ten sam koszt
W obu przypadkach przyspieszenie wynika z rozwiązania każdego stanu raz. Całkowity czas to liczba stanów pomnożona przez pracę wykonywaną dla jednego stanu.
Krótki test
Które podejście wypełnia tabelę od dołu do góry za pomocą pętli?
Podsumowanie: dwie drogi, jedno DP
Podproblemy można teraz buforować na dwa sposoby. Memoizacja korzysta z rekurencji od góry do dołu, a tabulacja z pętli od dołu do góry. Należy wybrać rozwiązanie, które jest czytelniejsze. ✨
Często zadawane pytania
Czy lekcja „Memoizacja kontra tabulacja” jest bezpłatna?
Tak — pełny tekst „Memoizacja kontra tabulacja” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Memoizacja kontra tabulacja”?
Dwa sposoby buforowania odpowiedzi podproblemów Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Memoizacja kontra tabulacja”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Memoizacja kontra tabulacja
- Definiowanie stanu i przejścia
- Wspinanie się po schodach i kombinacje monet
- Najdłuższy rosnący podciąg