დინამიური პროგრამირება (DP) ხსნის პრობლემებს გადაფარვადი ქვე-პრობლემებით და ოპტიმალური ქვე-სტრუქტურით ყოველი ქვე-პრობლემის ერთხელ გამოთვლით და შედეგის ხელმეორედ გამოყენებით. ორი სტილი არის memoization (ზემოდან-ქვემოთ) და tabulation (ქვემოდან-ზემოთ).
შინამი რეკურსია იმეორებს ერთსა და იმავე ქვე-პრობლემებს ექსპონენციალურად. DP ამ მნიშვნელობებს ხსნის ფიქსაციაში, ექსპონენციალური მუშაობის პოლინომიულზე ჩამობრლის შედეგად.
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 | |
|---|---|---|
| მიმართულება | ზემოდან-ქვემოთ რეკურსია | ქვემოდან-ზემოთ იტერაცია |
| ითვლის | მხოლოდ საჭირო მდგომარეობები | ყველა მდგომარეობა |
| რისკი | stack overflow | არაფერი |
| ადგილი | შეიძლება შემცირდეს | ხშირად O(1) რიგამდე შემცირებული |
ფიბონაჩი: O(2ⁿ) ნაივი O(n) დროდან, O(n) (ან O(1)) ადგილი.
DP გამოიყენეთ როდესაც ქვე-პრობლემები გადაფარია. ფრთხელი განსაზღვრეთ მდგომარეობა და რეკურენტება — ეს არის რთული ნაწილი. თუ ქვე-პრობლემები არ არის გადაფარი, ჩვეულებრივი divide-and-conquer საკმარისია.
DP გარდაქმნის ამოუშავებელ ექსპონენციალურ პრობლემებს — უმოკლეს გზა, რედაქტირების მანძილი, საფირი — ეფიკასურებებში.
მდგომარეობის და რეკურენტების ამოცნობის უნარი ერთ-ერთი ყველაზე ღირებული ალგორითმის ინტერვიუებში.
ის საფუძველი რეალური სისტემებიდან diff ინსტრუმენტებიდან ბიოინფორმატიკა მიმდევრობის გასწორებამდე.