কনটেন্টে যান

Dynamic programming — টেবিল কীভাবে উত্তর তৈরি করে

অধ্যায়ের সূচি · সহজ ব্যাখ্যা ও বাস্তব ব্যবহার · অনুশীলন ও সমাধান

DP-তে প্রতিটি cell একটি ছোট প্রশ্নের উত্তর রাখে। নতুন cell হিসাব করতে আগেই জানা cell ব্যবহার করি। আগে প্রশ্নটি কী, তারপর কোন cell থেকে কোন cell-এর মান আসছে, তা দেখো।

Grid paths — ওপরের ও বাঁয়ের উত্তর যোগ

একটি 3×3 grid-এ ওপরের বাঁ কোণ থেকে নিচের ডান কোণে যেতে হবে। শুধু right ও down চলা যায়। dp[r][c] মানে ওই ঘরে পৌঁছানোর পথসংখ্যা; তাই dp[r][c] = ওপরের মান + বাঁয়ের মান।

চার ধাপে পুরো path table

  1. ১. শুরুতে দাঁড়ানোর একটি উপায়

    চিহ্নিত ঘর: 1
    ·
    ·
    ·
    ·
    ·
    ·
    ·
    ·

    Base case dp[0][0] = 1। বিন্দু মানে এখনো হিসাব হয়নি।

  2. ২. প্রথম সারি

    1
    চিহ্নিত ঘর: 1
    চিহ্নিত ঘর: 1
    ·
    ·
    ·
    ·
    ·
    ·

    ওপরের ঘর নেই; শুধু বাঁ দিক থেকে আসা যায়। তাই দুটো মানই 1।

  3. ৩. দ্বিতীয় সারি

    1
    1
    1
    চিহ্নিত ঘর: 1
    চিহ্নিত ঘর: 2
    চিহ্নিত ঘর: 3
    ·
    ·
    ·

    বাঁ থেকে ডানে 1, তারপর 1+1 = 2, তারপর 1+2 = 3।

  4. ৪. শেষ সারি

    1
    1
    1
    1
    2
    3
    চিহ্নিত ঘর: 1
    চিহ্নিত ঘর: 3
    চিহ্নিত ঘর: 6

    মানগুলো 1, তারপর 2+1 = 3, তারপর 3+3 = 6। উত্তর 6টি পথ।

শেষ ঘরের 6 কোথা থেকে এলো:

flowchart TD
  top["ওপর: dp[1][2] = 3"] -->|নিচে আসা| result["dp[2][2] = 3 + 3 = 6"]
  left["বাঁয়ে: dp[2][1] = 3"] -->|ডানে আসা| result

ওপর থেকে আসা পথ আর বাঁ থেকে আসা পথ আলাদা; তাই যোগ করা যায়। যাচাই করার আরেক উপায়: মোট চার move-এ দুইটি right ও দুইটি down। চার জায়গায় দুইটি right বসানোর উপায় C(4,2)=6।

Coin change — আগের amount-এর সেরা উত্তর নাও

Coins [1,2,5] দিয়ে amount 11 বানাতে সর্বনিম্ন কয়টি coin লাগে? প্রতিটি coin যতবার দরকার ব্যবহার করা যায়। dp[a] হলো amount a-এর সর্বনিম্ন coin সংখ্যা।

Base case dp[0]=0। যে coin c ≤ a, শুধু সেটির জন্য dp[a−c]+1 candidate। তাই এই উদাহরণে dp[a] = 1 + min(dp[a−1], dp[a−2], dp[a−5]), তবে negative index-এর term বাদ দিতে হবে।

Amount হলো index; বাক্সে সর্বনিম্ন coin সংখ্যা

  1. শুরু — শুধু amount 0-এর উত্তর জানা

    চিহ্নিত ঘর: 00
    1∞
    2∞
    3∞
    4∞
    5∞
    6∞
    7∞
    8∞
    9∞
    10∞
    11∞

    ∞ মানে এখনো কোনো সমাধান পাওয়া যায়নি।

  2. Amount 5 পর্যন্ত হিসাব

    00
    11
    21
    32
    42
    চিহ্নিত ঘর: 51
    6∞
    7∞
    8∞
    9∞
    10∞
    11∞

    Amount 5-এ একটি 5-coin নিলেই হয়; পাঁচটি 1-coin নেওয়ার দরকার নেই।

  3. পুরো table — amount 11-এর উত্তর 3

    00
    11
    21
    32
    42
    51
    62
    72
    83
    93
    102
    চিহ্নিত ঘর: 113

    একটি সর্বোত্তম সমাধান 5+5+1।

প্রতিটি amount-এর হিসাব নিচে আছে। Candidate column-এ coin 1, 2, 5 নেওয়ার আগের amount-এর dp value দেখানো হয়েছে; শেষে একটি coin যোগ হয়।

Amount a আগের dp values 1 + min(...) একটি সর্বোত্তম বাছাই
1 dp[0]=0 1 1
2 dp[1]=1, dp[0]=0 1 2
3 dp[2]=1, dp[1]=1 2 2+1
4 dp[3]=2, dp[2]=1 2 2+2
5 dp[4]=2, dp[3]=2, dp[0]=0 1 5
6 dp[5]=1, dp[4]=2, dp[1]=1 2 5+1
7 dp[6]=2, dp[5]=1, dp[2]=1 2 5+2
8 dp[7]=2, dp[6]=2, dp[3]=2 3 5+2+1
9 dp[8]=3, dp[7]=2, dp[4]=2 3 5+2+2
10 dp[9]=3, dp[8]=3, dp[5]=1 2 5+5
11 dp[10]=2, dp[9]=3, dp[6]=2 3 5+5+1

Amount 11-এর তিনটি candidate-কে ছবিতে দেখলে:

flowchart TD
  a["dp[10] = 2"] -->|coin 1: মোট 3| result["dp[11] = min(3, 4, 3) = 3"]
  b["dp[9] = 3"] -->|coin 2: মোট 4| result
  c["dp[6] = 2"] -->|coin 5: মোট 3| result

শুধু coin সংখ্যা নয়, আসল coin-ও ফেরত পেতে হলে winning choice ধরে পিছিয়ে যাই। Tie হলে যেকোনো সর্বোত্তম choice নেওয়া যায়। এখানে coin 5 আগে বেছে নিচ্ছি:

flowchart LR
  a["amount 11"] -->|নাও 5| b["amount 6"]
  b -->|নাও 5| c["amount 1"]
  c -->|নাও 1| d["amount 0 · শেষ"]

জমা coin 5,5,1; সংখ্যা 3। DP table সেরা মান রাখে; winning choice-এর পথ আসল সমাধান ফিরিয়ে দেয়।

Memoization — একই প্রশ্নের উত্তর আবার হিসাব নয়

সাধারণ recursive fib(5)-এ প্রতিটি box একটি function call। একই label একাধিক box-এ আছে, কারণ একই প্রশ্নের উত্তর বারবার হিসাব হচ্ছে। মোট 15টি call।

flowchart TD
  a["fib(5)"] --> b["fib(4)"]
  a --> c["fib(3)"]
  b --> d["fib(3)"]
  b --> e["fib(2)"]
  c --> f["fib(2)"]
  c --> g["fib(1)"]
  d --> h["fib(2)"]
  d --> i["fib(1)"]
  e --> j["fib(1)"]
  e --> k["fib(0)"]
  f --> l["fib(1)"]
  f --> m["fib(0)"]
  h --> n["fib(1)"]
  h --> o["fib(0)"]

Memoization-এ প্রথমবার পাওয়া উত্তর cache-এ রাখি; পরের call একই প্রশ্ন করলে সেই উত্তর সরাসরি ফেরত দিই। নিচে বাঁয়ের call আগে চলে এবং base case-এর উত্তরও cache হয়। মোট 9টি call; ছয়টি আলাদা value হিসাব হয়, তিনটি cache hit।

flowchart TD
  a["fib(5)"] --> b["fib(4)"]
  a --> c["fib(3) · cache hit"]
  b --> d["fib(3)"]
  b --> e["fib(2) · cache hit"]
  d --> f["fib(2)"]
  d --> g["fib(1) · cache hit"]
  f --> h["fib(1)"]
  f --> i["fib(0)"]

Cache hit-এর নিচে আর subtree নেই। বড় n-এ এই ছোট পার্থক্যই বিশাল কাজ বাঁচায়।

n সাধারণ recursion-এর call Memoization-এর call, cache hit-সহ
5 15 9
10 177 19
20 21,891 39
50 40,730,022,147 99

এই সাধারণ fib(n−1)+fib(n−2) recursion-এ naive call সংখ্যা 2F(n+1)−1; memoized version-এ n≥2 হলে 2n−1। Function call মানেই নতুন state হিসাব নয়—cache hit-ও call হিসেবে গোনা হয়েছে।

নতুন DP-তে এই পাঁচটি প্রশ্ন করো

  1. State: প্রতিটি cell ঠিক কোন প্রশ্নের উত্তর রাখে?
  2. Base: কোন ছোট উত্তরগুলো আগে থেকেই জানা?
  3. Transition: কোন আগের cell থেকে বর্তমান উত্তর আসবে?
  4. Order: যাদের উত্তর লাগবে, তারা আগে হিসাব হচ্ছে তো?
  5. Answer: কোন cell-এ চূড়ান্ত মান, এবং choice ফিরিয়ে আনতে হবে কি?

Code লেখার আগে ছোট input-এ পুরো table ভরো। Grid-এ একটি দেয়াল বসালে base/transition কী বদলায়, অথবা coin 1 বাদ দিলে কোন amount অসম্ভব হয়—এ দুটি পরিবর্তন নিজে trace করলে state-এর অর্থ আরও পরিষ্কার হবে।