ডায়নামিক প্রোগ্রামিং (DP) overlapping subproblems এবং optimal substructure সহ সমস্যা সমাধান করে প্রতিটি সাবপ্রবলেম একবার গণনা করে এবং ফলাফল পুনঃব্যবহার করে। দুটি শৈলী হল memoization (top-down) এবং tabulation (bottom-up)।
নিরীহ recursion একই সাবপ্রবলেম exponentially পুনরায় গণনা করে। DP সেগুলি cache করে, exponential কাজকে polynomial এ পরিণত করে।
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 recursion | bottom-up iteration |
| গণনা করে | শুধুমাত্র প্রয়োজনীয় states | সকল states |
| ঝুঁকি | stack overflow | কোনো নেই |
| স্পেস | trimmed করা যায় | প্রায়ই O(1) rows এ হ্রাসযোগ্য |
ফিবোনাচ্চি: O(2ⁿ) নিরীহ থেকে O(n) সময়, O(n) (বা O(1)) স্পেস।
DP ব্যবহার করুন যখন subproblems overlap করে। state এবং recurrence সতর্কতার সাথে সংজ্ঞায়িত করুন — এটি কঠিন অংশ। যদি subproblems overlap না করে, সাধারণ divide-and-conquer যথেষ্ট।
DP intractable exponential সমস্যা — shortest paths, edit distance, knapsack — দক্ষ সমস্যায় রূপান্তরিত করে।
state এবং recurrence চিহ্নিত করার দক্ষতা algorithm interviews এ সবচেয়ে মূল্যবান দক্ষতাগুলির মধ্যে একটি।
এটি diff tools থেকে bioinformatics sequence alignment পর্যন্ত বাস্তব সিস্টেমের ভিত্তি।