Memoizacja

Lekcja 4 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.

Memoizacja to technika optymalizacji stosowana w programowaniu dynamicznym, która przyspiesza działanie programów przez buforowanie wyników kosztownych wywołań funkcji i zwracanie buforowanego wyniku, gdy ponownie pojawią się te same dane wejściowe.

Aby zaimplementować memoizację, możesz utworzyć słownik do przechowywania już obliczonych wyników, w którym kluczami są argumenty wejściowe, a wartościami odpowiadające im wyniki wyjściowe. Zanim obliczysz wynik funkcji, możesz najpierw sprawdzić, czy dane wejściowe zostały już obliczone i zapisane w słowniku. Jeśli tak, możesz zwrócić buforowany wynik zamiast obliczać go ponownie. W przeciwnym razie obliczasz wynik i zapisujesz go w słowniku.

Do implementacji memoizacji można również użyć list.

Memoizacja może znacznie przyspieszyć algorytmy programowania dynamicznego, zwłaszcza gdy występuje wiele nakładających się podproblemów.

Wyzwanie

Łatwy

Napisz funkcję Python o nazwie fib, która oblicza n-tą liczbę Fibonacciego z użyciem memoizacji.

Użyj słownika memo, aby przechowywać już obliczone liczby Fibonacciego.
Przed obliczeniem n-tej liczby Fibonacciego sprawdź, czy została już obliczona i zapisana w memo.
Jeśli tak, zwróć wynik z pamięci podręcznej. W przeciwnym razie oblicz n-tą liczbę Fibonacciego za pomocą zależności rekurencyjnej fib(n) = fib(n-1) + fib(n-2) i zapisz wynik w słowniku do późniejszego wykorzystania.