algorithm
Tillämpningar av dynamisk programmering

Introduktion

Anmärkningar

Fibonacci-nummer

Fibonacci-nummer är ett huvudämne för dynamisk programmering eftersom det traditionella rekursiva tillvägagångssättet gör en hel del upprepade beräkningar. I dessa exempel använder jag basfallet f(0) = f(1) = 1 .

Här är ett exempel på rekursivt träd för fibonacci(4) , notera de upprepade beräkningarna:

Icke-dynamisk programmering O(2^n) Runtime Complexity, O(n) Stack complexity

def fibonacci(n):
    if n < 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

Detta är det mest intuitiva sättet att skriva problemet. Högst upp kommer stackutrymmet att vara O(n) när du går ner till den första rekursiva grenen som ringer till fibonacci(n-1) tills du träffar basfallet n < 2 .

O(2^n) runtime complexity proof som kan ses här: Computational complexity of Fibonacci Sequence . Den viktigaste punkten att notera är att runtime är exponentiell, vilket innebär att runtime för detta kommer att fördubblas för varje efterföljande term, fibonacci(15) kommer att ta dubbelt så lång tid som fibonacci(14) .

Memoized O(n) Runtime Complexity, O(n) Space complexity, O(n) Stack complexity

memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1

def fibonacci(n):
    if len(memo) > n:
        return memo[n]

    result = fibonacci(n-1) + fibonacci(n-2)
    memo.append(result) # f(n) = f(n-1) + f(n-2)
    return result

Med det memiserade tillvägagångssättet introducerar vi en matris som kan tänkas som alla tidigare funktionssamtal. memo[n] är resultatet av funktionen samtalsbortfall fibonacci(n) . Detta tillåter oss att handla rymdkomplexitet för O(n) för en O(n) runtime eftersom vi inte längre behöver beräkna duplicerade funktionssamtal.

Iterativ dynamisk programmering O(n) Runtidskomplexitet, O(n) Rymdkomplexitet, Ingen rekursiv stack

def fibonacci(n):
    memo = [1,1] # f(0) = 1, f(1) = 1

    for i in range(2, n+1):
         memo.append(memo[i-1] + memo[i-2])

    return memo[n]

Om vi delar upp problemet i dess kärnelement kommer du att märka att för att beräkna fibonacci(n) behöver vi fibonacci(n-1) och fibonacci(n-2) . Vi kan också märka att vårt basfall kommer att visas i slutet av det rekursiva trädet som ses ovan.

Med denna information är det nu vettigt att beräkna lösningen bakåt, börja vid basfallen och arbeta uppåt. För att beräkna fibonacci(n) beräknar vi först alla siffror för upp till och igenom n .

Denna huvudfördel här är att vi nu har eliminerat den rekursiva stacken medan vi håller O(n) körtiden. Tyvärr har vi fortfarande en O(n) rymdkomplexitet men det kan också ändras.

Avancerad Iterativ dynamisk programmering O(n) Runtidskomplexitet, O(1) Rymdkomplexitet, Ingen rekursiv stack

def fibonacci(n):
    memo = [1,1] # f(1) = 1, f(2) = 1

    for i in range (2, n):
        memo[i%2] = memo[0] + memo[1]

    return memo[n%2]

Som nämnts ovan startar den iterativa dynamiska programmeringsmetoden från basfallen och fungerar till slutresultatet. Den viktigaste observationen att göra för att komma till rymdkomplexiteten till O(1) (konstant) är samma observation som vi gjorde för den rekursiva stacken - vi behöver bara fibonacci(n-1) och fibonacci(n-2) att bygga fibonacci(n) Detta innebär att vi bara behöver spara resultaten för fibonacci(n-1) och fibonacci(n-2) när som helst i vår iteration.

För att lagra dessa två senaste resultat använder jag en matris i storlek 2 och vänder helt enkelt till vilket index jag tilldelar genom att använda i % 2 som kommer att växla så: 0, 1, 0, 1, 0, 1, ..., i % 2 .

Jag lägger till båda indexen för matrisen tillsammans eftersom vi vet att tillägget är kommutativt ( 5 + 6 = 11 och 6 + 5 == 11 ). Resultatet tilldelas sedan den äldre av de två fläckarna (betecknas med i % 2 ). Det slutliga resultatet lagras sedan vid positionen n%2

anteckningar

• Det är viktigt att notera att det ibland kan vara bäst att ta fram en iterativ memoized-lösning för funktioner som utför stora beräkningar upprepade gånger eftersom du kommer att bygga upp en cache för svaret på funktionssamtal och efterföljande samtal kan vara O(1) om det har redan beräknats.