ডাইনামিক প্রোগ্রামিং

Dynamic Programming (DP) কী?

DP হলো এমন পদ্ধতি যেখানে উপ-সমস্যার সমাধান সংরক্ষণ করা হয় যাতে একই গণনা বারবার না করতে হয়। এটি Overlapping Subproblems আছে এমন সমস্যার জন্য কার্যকর।

বাস্তব উদাহরণ

ধরুন আপনি ঢাকা থেকে চট্টগ্রাম যাচ্ছেন এবং প্রতিটি শহরের মধ্যে দূরত্ব গণনা করছেন। একবার গণনা করলে আর করতে হবে না — এটাই DP!

Fibonacci — DP উদাহরণ

# ❌ Without DP (ধীর — বারবার একই গণনা)
def fib_slow(n):
    if n <= 1: return n
    return fib_slow(n-1) + fib_slow(n-2)

# ✅ With DP (দ্রুত — ফলাফল সংরক্ষণ)
def fib_fast(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib_fast(n-1) + fib_fast(n-2)
    return memo[n]

print(fib_fast(50))  # তাৎক্ষণিক!

দুটি পদ্ধতি

• Top-Down (Memoization) — Recursion + Cache
• Bottom-Up (Tabulation) — Loop দিয়ে নিচ থেকে তৈরি