Optymalizacja pamięci
Lekcja 12 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.
W programowaniu dynamicznym często używamy tabeli lub macierzy do przechowywania rozwiązań podproblemów. W niektórych przypadkach tabela może jednak być zbyt duża i zużywać zbyt dużo pamięci. Właśnie wtedy przydaje się optymalizacja pamięci. Techniki optymalizacji pamięci służą do zmniejszania ilości pamięci potrzebnej do rozwiązania problemu programowania dynamicznego.
Jedną z popularnych technik optymalizacji pamięci jest używanie tablic kroczących, znanych również jako tablice przesuwne. Zamiast przechowywać całą tabelę, przechowuje się tylko jej część naraz, a poprzednie wartości są usuwane w miarę obliczania nowych. Może to znacząco zmniejszyć ilość pamięci potrzebnej do rozwiązania problemu.
Wyzwanie
TrudnyW tym wyzwaniu otrzymujesz tablicę liczb całkowitych. Twoim zadaniem jest znalezienie długości najdłuższego rosnącego podciągu (LIS) w tablicy. Rosnący podciąg to ciąg liczb z tablicy, w którym każda liczba jest większa od poprzedniej. LIS to najdłuższy taki podciąg. Musisz zaimplementować rozwiązanie z użyciem technik optymalizacji pamięci.
Spróbuj swoich sił
def lis_length(arr):
# 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