Dinamik proqramlaşdırma (DP) hər təkrarlanan alt məsələni bir dəfə həll edir və cavabı yadda saxlayır. Eksponensial rekursiya polinomial cədvəl doldurmasına çevrilir.

DP nə vaxt işləyir

  • Optimal alt struktur: böyük məsələnin optimal cavabı kiçik məsələlərin optimal cavablarından qurulur.
  • Üst-üstə düşən alt məsələlər: eyni kiçik məsələ dəfələrlə yaranır.

Böl və hökm sürdə hissələr müstəqildir, burada isə təkrarlanır. Aclıqlı alqoritmdən fərqi: DP bütün alt cavabları nəzərə alır və lokal seçimin təhlükəsizliyini sübut etməyə ehtiyac yoxdur.

fib(5) çağırış ağacı: təkrarlanan alt məsələlər qırmızıdır
fib(5) çağırış ağacı: təkrarlanan alt məsələlər qırmızıdır

Sadə rekursiya eksponensialdır

python
calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(20), calls)
calls = 0
fib(25)
print("fib(25) calls:", calls)

fib(20) 21 891 çağırış edir, fib(25) isə 242 785: təxminən O(1.6^n).

Yuxarıdan-aşağı: memoizasiya