DP প্যারাডাইম — মেমোয়াইজেশন বনাম ট্যাবুলেশন

১ · DP কখন প্রযোজ্য — দুটি শর্ত

DSA কোর্সে আপনি ইতিমধ্যে কয়েকটি DP সমস্যা (যেমন ফিবোনাচি, কয়েন চেঞ্জ) দেখে থাকতে পারেন। এই কোর্স ধরে নেয় আপনি DP-এর মৌলিক ধারণার সাথে পরিচিত — এখানে আমরা সরাসরি যাচাই করব ঠিক কেন DP কাজ করে এবং মেমোয়াইজেশন বনাম ট্যাবুলেশন বেছে নেওয়ার সিদ্ধান্তে যাব। একটি সমস্যায় DP প্রযোজ্য হওয়ার জন্য দুটি শর্ত পূরণ হতে হয়:

দুটো শর্তই থাকলে তবেই "প্রতিটি সাবপ্রবলেম একবার সমাধান করে ফলাফল জমা রাখা" একটি লাভজনক কৌশল হয়ে ওঠে — এবং এটাই DP-এর মূল ধারণা। গ্রিডি অ্যালগরিদমের (M5) সাথে পার্থক্য মনে রাখুন — গ্রিডিতে প্রতি ধাপে একটিই স্থানীয়-সেরা পছন্দ করা হয় এবং কখনো ফিরে দেখা হয় না, কিন্তু DP-তে সব সম্ভাব্য সাবপ্রবলেমের উত্তর গণনা করে রাখা হয় (তাই DP অনেক বেশি সমস্যায় প্রযোজ্য, কিন্তু গ্রিডির চেয়ে ধীর)।

২ · উদাহরণ সমস্যা — কয়েন কম্বিনেশন গোনা

ধরুন coins হলো কয়েকটি ভিন্ন মূল্যমানের কয়েন (প্রতিটির যথেষ্ট সরবরাহ আছে ধরে নিন), এবং আমরা জানতে চাই amount পরিমাণ তৈরি করার কতগুলো ভিন্ন কম্বিনেশন সম্ভব (ক্রম গুরুত্বপূর্ণ নয় — ১+২ ও ২+১ একই কম্বিনেশন)। রাজ্য সংজ্ঞায়িত করি $W(i, a)$ = coins[i:] (অর্থাৎ $i$-তম কয়েন থেকে শুরু করে বাকি সব কয়েন, অসীম সরবরাহে) ব্যবহার করে $a$ পরিমাণ তৈরি করার কম্বিনেশন সংখ্যা।

$$ W(i, a) = \begin{cases} 1 & \text{যদি } a = 0 \\ 0 & \text{যদি } a < 0 \text{ অথবা } (i = n \text{ এবং } a > 0) \\ W(i+1,\, a) \;+\; W(i,\, a - c_i) & \text{অন্যথায়} \end{cases} $$

প্রথম রিকার্সিভ টার্ম W(i+1, a) মানে "$c_i$ কয়েনটি একেবারেই ব্যবহার না করা" (পরের কয়েনে চলে যাওয়া)। দ্বিতীয় টার্ম W(i, a - c_i) মানে "$c_i$ কয়েনের অন্তত একটি ব্যবহার করা" (একই $i$-তে থেকে যাওয়া, কারণ কয়েনটি আবার ব্যবহার করা যাবে)। এই দুই বিকল্প একে অপরের সাথে ওভারল্যাপ করে না, তাই যোগ করলেই মোট কম্বিনেশন পাওয়া যায় — এটাই এখানকার অপটিমাল সাবস্ট্রাকচার আর্গুমেন্ট (আসলে এটি একটি "গণনা" সমস্যা, "অপটিমাইজেশন" নয়, কিন্তু একই নীতি প্রযোজ্য: বড় প্রবলেমের উত্তর ছোট সাবপ্রবলেমের উত্তর থেকে সরাসরি গঠন করা যায়)। আর W(i, a) অবস্থাটি বহু ভিন্ন রিকার্সিভ পথ থেকে বারবার আসতে পারে — এটাই ওভারল্যাপিং সাবপ্রবলেম।

৩ · মেমোয়াইজেশন (টপ-ডাউন)

মেমোয়াইজেশনে আমরা রিকারেন্সটি ঠিক যেমন আছে তেমনই একটি রিকার্সিভ ফাংশন হিসেবে লিখি, শুধু একটি ডিকশনারিতে (cache) প্রতিটি $(i, a)$-এর উত্তর জমা রাখি যাতে একই অবস্থা দ্বিতীয়বার এলে পুনরায় গণনা না করে সরাসরি cache থেকে ফেরত দেওয়া যায়।

৪ · ট্যাবুলেশন (বটম-আপ)

ট্যাবুলেশনে কোনো রিকার্সন নেই — বরং একটি টেবিল dp[i][a] তৈরি করে সবচেয়ে ছোট সাবপ্রবলেম (i = n, অর্থাৎ কোনো কয়েন বাকি নেই) থেকে শুরু করে বড় দিকে ($i = n-1, n-2, \dots, 0$) ইটারেটিভভাবে পূরণ করা হয়। একই $i$-এর ভেতরে a ছোট থেকে বড় দিকে যেতে হয়, কারণ dp[i][a] নির্ভর করে dp[i][a - coins[i]]-এর উপর (একই সারিতে, কিন্তু ছোট a)।

def count_ways_naive(coins, i, a, counter):
    # নেইভ রিকার্সন -- কোনো cache নেই, একই (i, a) বহুবার গণনা হয়
    counter[0] += 1
    if a == 0:
        return 1
    if a < 0 or i == len(coins):
        return 0
    skip = count_ways_naive(coins, i + 1, a, counter)       # coins[i] একদম ব্যবহার না করা
    take = count_ways_naive(coins, i, a - coins[i], counter) # coins[i]-এর অন্তত একটি ব্যবহার করা
    return skip + take

def count_ways_memo(coins, i, a, cache, counter):
    # মেমোয়াইজেশন -- ঠিক একই রিকারেন্স, শুধু cache যোগ করা হয়েছে
    counter[0] += 1
    if a == 0:
        return 1
    if a < 0 or i == len(coins):
        return 0
    key = (i, a)
    if key in cache:
        return cache[key]
    result = (count_ways_memo(coins, i + 1, a, cache, counter)
              + count_ways_memo(coins, i, a - coins[i], cache, counter))
    cache[key] = result
    return result

def count_ways_tab(coins, amount):
    # ট্যাবুলেশন -- কোনো রিকার্সন নেই, ইটারেটিভভাবে টেবিল পূরণ
    n = len(coins)
    dp = [[0] * (amount + 1) for _ in range(n + 1)]
    for a in range(amount + 1):
        dp[n][a] = 1 if a == 0 else 0
    for i in range(n - 1, -1, -1):
        for a in range(amount + 1):
            ways = dp[i + 1][a]
            if a - coins[i] >= 0:
                ways += dp[i][a - coins[i]]
            dp[i][a] = ways
    return dp[0][amount]

test_cases = [
    ([1, 2, 5], 5),
    ([1, 2, 5], 11),
    ([2, 3, 7], 12),
    ([1, 5, 10, 25], 30),
]

print(f"{'coins':>18} | {'amount':>6} | {'naive':>6} | {'memo':>6} | {'tab':>6}")
for coins, amount in test_cases:
    n_counter = [0]
    m_counter = [0]
    r_naive = count_ways_naive(coins, 0, amount, n_counter)
    r_memo = count_ways_memo(coins, 0, amount, {}, m_counter)
    r_tab = count_ways_tab(coins, amount)
    assert r_naive == r_memo == r_tab, "মিসম্যাচ!"
    print(f"{str(coins):>18} | {amount:>6} | {r_naive:>6} | {r_memo:>6} | {r_tab:>6}")

print("\nতিনটি বাস্তবায়নই সব টেস্ট কেসে অভিন্ন উত্তর দিয়েছে।")

৫ · ওভারল্যাপিং সাবপ্রবলেম বাস্তবে কতটা প্রভাব ফেলে

"ওভারল্যাপিং সাবপ্রবলেম" শুধু তত্ত্বকথা নয় — নিচের কোড সেলে coins = [1, 5, 10, 25] রেখে amount বাড়িয়ে বাড়িয়ে নেইভ রিকার্সনের মোট ফাংশন-কল সংখ্যা এবং মেমোয়াইজড ভার্সনের কল সংখ্যা ও cache-এ জমা হওয়া ইউনিক অবস্থার সংখ্যা গুনে তুলনা করা হয়েছে।

coins = [1, 5, 10, 25]
print(f"{'amount':>6} | {'naive calls':>12} | {'memo calls':>11} | {'unique states':>13}")
for amount in [10, 20, 30, 40, 50]:
    n_counter = [0]
    m_counter = [0]
    cache = {}
    count_ways_naive(coins, 0, amount, n_counter)
    count_ways_memo(coins, 0, amount, cache, m_counter)
    print(f"{amount:>6} | {n_counter[0]:>12} | {m_counter[0]:>11} | {len(cache):>13}")