Δυναμικός προγραμματισμός (DP) λύνει προβλήματα με overlapping subproblems και optimal substructure υπολογίζοντας κάθε υποπρόβλημα μία φορά και επαναχρησιμοποιώντας το αποτέλεσμα. Οι δύο στυλ είναι memoization (top-down) και tabulation (bottom-up).
Η αφελής αναδρομή υπολογίζει εκ νέου τα ίδια υποπροβλήματα εκθετικά. Το DP τα αποθηκεύει σε cache, συμπτύσσοντας εκθετική εργασία σε πολυώνυμη.
from functools import lru_cache
@lru_cache(maxsize=None) # cache results automatically
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2) # each n computed once
def fib_table(n):
if n < 2:
return n
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2]) # build up from base cases
return dp[n]
| Memoization | Tabulation | |
|---|---|---|
| Κατεύθυνση | αναδρομή top-down | επανάληψη bottom-up |
| Υπολογίζει | μόνο τις απαιτούμενες καταστάσεις | όλες τις καταστάσεις |
| Κίνδυνος | stack overflow | κανένας |
| Χώρος | μπορεί να περιοριστεί | συχνά ανάγεται σε σειρές O(1) |
Fibonacci: από O(2ⁿ) αφελή σε O(n) χρόνο, O(n) (ή O(1)) χώρο.
Χρησιμοποιήστε DP όταν τα υποπροβλήματα επικαλύπτονται. Ορίστε την κατάσταση και τη σχέση αναδρομής προσεκτικά — αυτό είναι το δύσκολο μέρος. Αν τα υποπροβλήματα δεν επικαλύπτονται, ο απλός divide-and-conquer αρκεί.
Το DP μετατρέπει άλυτα εκθετικά προβλήματα — συντομότερες διαδρομές, edit distance, knapsack — σε αποδοτικά.
Η δεξιότητα της αναγνώρισης κατάστασης και σχέσης αναδρομής είναι ανάμεσα στις πολυτιμότερες σε συνεντεύξεις αλγορίθμων.
Βρίσκεται στη βάση πραγματικών συστημάτων από εργαλεία diff έως στοίχιση ακολουθιών βιοπληροφορικής.