Memoizacja bez rekurencji
Lekcja 5 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.
W poprzedniej lekcji poznaliśmy memoizację i dowiedzieliśmy się, jak może ona pomóc poprawić złożoność czasową naszych rozwiązań rekurencyjnych. W tej lekcji przyjrzymy się, jak używać rekurencji z memoizacją, aby rozwiązywać problemy wydajniej.
Rekurencja to technika programowania, w której funkcja wywołuje samą siebie, aby rozwiązać problem. Rozwiązania rekurencyjne mogą być bardzo eleganckie i intuicyjne, ale mogą też być nieefektywne, zwłaszcza gdy ta sama funkcja jest wywoływana wielokrotnie z tymi samymi argumentami. Właśnie tu przydaje się memoizacja. Zapisując wyniki wcześniejszych wywołań funkcji, możemy uniknąć zbędnych obliczeń i znacznie poprawić wydajność naszych rozwiązań rekurencyjnych.
Wyzwanie
ŁatwyZałóżmy, że możesz wspinać się po 1 lub 2 stopniach naraz.
Napisz funkcję o nazwie count_ways, która przyjmuje liczbę całkowitą n i zwraca liczbę sposobów na pokonanie schodów składających się z n stopni.
Funkcja powinna być zapamiętująca, aby uniknąć powtarzania obliczeń.
W tym wyzwaniu unikaj rekurencji!
Spróbuj swoich sił
def count_ways(n):
# TODO: napisz tutaj swój kodWszystkie 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