Dynamic Programming — একবার হিসাব, বারবার ব্যবহার

লক্ষ্য: দুই বাংলা শব্দের সম্পাদনা-পথ চোখে দেখা, আর coin change-এর দুই প্রশ্নের পার্থক্য কোডে বাঁধা।

def edit_distance_matrix(s1: str, s2: str):
    """পূর্ণ (len(s1)+1)x(len(s2)+1) matrix ফেরায় — traceback-এর জন্য"""
    d = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    for i in range(len(s1) + 1):
        d[i][0] = i                      # s2 খালি: সব delete
    for j in range(len(s2) + 1):
        d[0][j] = j                      # s1 খালি: সব insert
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1]:
                d[i][j] = d[i - 1][j - 1]           # match — free
            else:
                d[i][j] = 1 + min(d[i - 1][j],      # delete from s1
                                  d[i][j - 1],      # insert into s1
                                  d[i - 1][j - 1])  # replace
    return d


def trace_alignment(s1: str, s2: str):
    """matrix + traceback → (distance, ops list, aligned pair)"""
    d = edit_distance_matrix(s1, s2)
    i, j = len(s1), len(s2)
    ops = []
    top, bot = [], []
    while i > 0 or j > 0:
        if i > 0 and j > 0 and s1[i - 1] == s2[j - 1]:
            ops.append('match'); top.append(s1[i - 1]); bot.append(s2[j - 1])
            i, j = i - 1, j - 1
        elif i > 0 and j > 0 and d[i][j] == d[i - 1][j - 1] + 1:
            ops.append(f'replace {s1[i-1]}→{s2[j-1]}')
            top.append(s1[i - 1]); bot.append(s2[j - 1])
            i, j = i - 1, j - 1
        elif i > 0 and d[i][j] == d[i - 1][j] + 1:
            ops.append(f'delete {s1[i-1]}')
            top.append(s1[i - 1]); bot.append('-')
            i -= 1
        else:
            ops.append(f'insert {s2[j-1]}')
            top.append('-'); bot.append(s2[j - 1])
            j -= 1
    return d[len(s1)][len(s2)], ops[::-1], (''.join(top[::-1]), ''.join(bot[::-1]))


def coin_min(amount: int, coins) -> int:
    dp = [float('inf')] * (amount + 1); dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount]


def coin_count(amount: int, coins) -> int:
    dp = [1] + [0] * amount
    for c in coins:                       # coin outside = combinations
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]


if __name__ == '__main__':
    # ---------- bangla words ----------
    w1, w2 = 'বইখানা', 'বইটা'
    dist, ops, aligned = trace_alignment(w1, w2)
    print(f'"{w1}" → "{w2}"  distance = {dist}')
    for op in ops:
        print(f'   {op}')
    print(f'   {aligned[0]}')
    print(f'   {aligned[1]}')

    assert trace_alignment('kitten', 'sitting')[0] == 3
    assert trace_alignment('flaw', 'lawn')[0] == 2
    assert trace_alignment('', 'abc')[0] == 3

    # ---------- coin change ----------
    coins = [1, 5, 6, 9]

    def _ways(cs, i, amt):               # combination-counting oracle
        if amt == 0:
            return 1
        if amt < 0 or i == 0:
            return 0
        return _ways(cs, i - 1, amt) + _ways(cs, i, amt - cs[i - 1])

    def brute_min(amount):
        if amount == 0:
            return 0
        best = float('inf')
        for c in coins:
            if c <= amount:
                best = min(best, brute_min(amount - c) + 1)
        return best

    for amt in (0, 10, 11, 17):
        gm, gc = coin_min(amt, coins), coin_count(amt, coins)
        assert gm == brute_min(amt), (amt, gm)
        assert gc == _ways(coins, len(coins), amt), (amt, gc)
        print(f'amount {amt:>2}: min-coins={gm}  ways={gc} (oracle-matched)')

প্রত্যাশিত output:

"বইখানা" → "বইটা"  distance = 3
   match
   match
   delete খ
   delete া
   replace ন→ট
   match
   বইখানা
   বই--টা
amount  0: min-coins=0  ways=1 (oracle-matched)
amount 10: min-coins=2  ways=5 (oracle-matched)
amount 11: min-coins=2  ways=6 (oracle-matched)
amount 17: min-coins=3  ways=12 (oracle-matched)

নিজে বাড়ান:

১. Operation cost ভিন্ন করুন (replace=1.5, insert/delete=1) — weighted edit distance; spell-checker-এ keyboard-distance cost যোগ করুন। ২. LCS (longest common subsequence)-এ adapt করুন — diff tools-এর মূল ইঞ্জিন; alignment-এ match-only প্রিন্ট। ৩. coin_min-এ reconstruction যোগ করুন — কোন কোন coin নেওয়া হলো parent-pointer array দিয়ে।