Programowanie dynamiczne #1

Zadanie – Longest Increasing Sequence

Rozwiązanie: programowanie dynamiczne

Programowanie dynamiczne polega na rozwiązaniu skomplikowanego problemu poprzez jego rozbicie na mniejsze podproblemy, obliczenie wyników dla nich, a następnie wykorzystanie tych wyników do uzyskania rozwiązania problemu głównego.

Dla Longest Increasing Sequence można zastosować następujące podejście: jeśli dysponujemy ciągiem A oraz znamy wartość L (najdłuższy podciąg kończący się na każdym elemencie), to tę wiedzę można wykorzystać do obliczenia wartości L po dodaniu nowego elementu do ciągu.

Rozważmy następującą sytuację:

Dla ciągu A = {5,1,4,2 } z wartościami L = {1, 1, 2, 2 } (najdłuższe podciągi dla każdej pozycji) określić trzeba wartość L po dodaniu liczby 3.

Analiza możliwości:

• {5,3}: najdłuższy podciąg ma długość 1. Liczba 3 jest mniejsza niż 5, więc nie przedłuża tego ciągu.
• {1, 3}: ciąg o długości 1 kończący się na 1. Ponieważ 3>1, podciąg można wydłużyć do długości 2.
• {X,4,3}: dwuelementowy ciąg z ostatnim elementem 4. Liczba 3 jest mniejsza niż 4, więc ciągu nie można przedłużyć.
• {X,2,3}: ostatni element ciągu o długości 2 wynosi 2. Ponieważ 3>2, ciąg można wydłużyć do długości 3.

Po dodaniu liczby 3 można przedłużyć dwa istniejące podciągi. Najdłuższy możliwy podciąg uzyskany po tej operacji ma długość 3.

Analogiczny proces zastosowano w sytuacji poniżej:

Obecny jest ciąg o długości 3, zakończony wartością 3. Nowa wartość wynosi 9, którą jest większa od 3, zatem ciąg można przedłużyć do {X, X, 3, 9}.

Ogólny wzór na maksymalną długość podciągu rosnącego ma postać: L(i) =MAX(L(j) | j < i, A[j] < A[i]) + 1

Aby odtworzyć cały ciąg (a nie tylko jego długość), dla każdego podciągu należy przechowywać indeks elementu poprzedniego:

Kod Python oraz c++

def LongestIncreasingSequence( dane ):
    L = [ 0 for a in dane]
    Ref = [ -1 for a in dane]
    maxCount=0
    currentMaxIndex = -1


    for i, val_i in enumerate(dane):
        for j in range(0,i):
            val_j = dane[j]
            if val_i <= val_j:
                continue;
            if L[j]+1 > L[i]:
                L[i] = L[j]+1
                Ref[i] = j
        if L[i] > maxCount:
            maxCount = L[i]
            currentMaxIndex = i


    vec = [];
    while currentMaxIndex != -1:
        vec.insert(0,dane[currentMaxIndex])
        currentMaxIndex = Ref[currentMaxIndex]
    return vec

#include <iostream>
#include <algorithm>

using namespace std;

vector<int> LongestIncreasingSequence( vector<int>& dane )
{
    int ilosc = dane.size();
    vector<int> L(ilosc,0);
    vector<int> Ref(ilosc,-1);

    int maxCount=0, currentMaxIndex = -1;

    for ( int i = 0; i < ilosc; ++i )
    {
        for ( int j = 0; j < i; ++j )
        {
            if ( dane[i] <= dane[j] ) continue;
            if ( L[j]+1 > L[i] )
            {
                L[i] = L[j]+1;
                Ref[i] = j;
            }
        }
        if ( L[i] > maxCount ) {
            maxCount = L[i];
            currentMaxIndex = i;
        }
    }

    vector<int> vec;
    while (currentMaxIndex != -1) {
        vec.push_back(dane[currentMaxIndex]);
        currentMaxIndex = Ref[currentMaxIndex];
    }
    std::reverse(vec.begin(),vec.end());

    return vec;
}

Analiza złożoności

Alokacja pamięci dla tablicy najdłuższych podciągów wymaga złożoności pamięciowej O(N) (przechowywanie dwóch elementów dla każdej pozycji).

Złożoność czasowa wynosi O(N^2). Algorytm przechodzi przez N elementów ciągu, a dla każdego elementu sprawdza wszystkie poprzednie elementy w celu znalezienia maksymalnego podciągu, który można przedłużyć.

Wideo explicite [EN]