Fibonacci (DP)

O(n)

Fibonacciho čísla — 0, 1, 1, 2, 3, 5, 8, … — jsou definována tak, že každý člen je součtem dvou předchozích. Naivní rekurzivní definice přepočítává stejné hodnoty exponenciálněkrát; dynamické programování to napraví tím, že vyplní tabulku jednou, zleva doprava: nastav dva základní případy a pak každá buňka sečte dvě vlevo od sebe. To je lineární čas a učebnicový první příklad převedení překrývajících se podproblémů na prostou smyčku. Stejná jednořádková tabulace stojí za schody, dlážděním a dalšími lineárními rekurencemi. (Reálně jsou potřeba jen poslední dvě hodnoty, takže paměť lze zredukovat na O(1).)

DP tabulka
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Nasaď základní případy: F(0) = 0 a F(1) = 1.
  2. Pro každý další index sečti dvě buňky hned vlevo od něj.
  3. Ulož výsledek a posuň se o buňku doprava.
  4. Poslední buňka drží F(n) — spočítané jediným lineárním průchodem.

Pseudokód

1fibonacci(n):                       # O(n)2  dp[0] ← 0,  dp[1] ← 1              # base cases3  for i from 2 to n:4    dp[i] ← dp[i-1] + dp[i-2]        # sum the previous two5  return dp[n]6  # linear DP replaces exponential recursion