নতুনদের জন্য dynamic programming: ধাপে ধাপে পদ্ধতি

Dynamic programming (DP) সমস্যাকে ছোট overlapping উপসমস্যায় ভেঙে প্রতিটি একবার সমাধান করে উত্তর পুনর্ব্যবহার করে। এটি অনেক exponential recursive সমাধানকে polynomial করে।

DP কখন খাটে?

দুটি ধর্ম খুঁজুন:

১. Overlapping উপসমস্যা: একই ছোট প্রশ্ন বহুবার জিজ্ঞেস করা হয়। ২. Optimal substructure: পুরোটির সেরা উত্তর অংশগুলোর সেরা উত্তর থেকে গড়া যায়।

সাধারণ ভাষা: "কত উপায়ে", "ন্যূনতম খরচ", "সর্বোচ্চ মান", "সম্ভব কি", "দীর্ঘতম/সংক্ষিপ্ততম ক্রম"।

পুনরাবৃত্তিযোগ্য পদ্ধতি

১. State ঠিক করুন: dp[i] (বা dp[i][j]) সহজ কথায় কী বোঝায়? ২. Recurrence লিখুন: একটি state ছোট state-এর ওপর কীভাবে নির্ভর করে? ৩. Base case ঠিক করুন। ৪. ক্রম বাছুন: memoization দিয়ে top-down, বা table দিয়ে bottom-up। ৫. উত্তর খুঁজুন: কোন state-এ আছে? ৬. Recurrence শুধু কয়েকটি state পেছনে তাকালে space অপ্টিমাইজ করুন।

উদাহরণ ১: climbing stairs

একবারে ১ বা ২ ধাপ ওঠা যায়। n-তম ধাপে পৌঁছানোর কত উপায়?

• State: dp[i] = i-তম ধাপে পৌঁছানোর উপায়ের সংখ্যা।
• Recurrence: শেষ চাল i - 1 বা i - 2 থেকে এসেছে, তাই dp[i] = dp[i-1] + dp[i-2]।
• Base: dp[0] = 1, dp[1] = 1।

function climbStairs(n) {
  let a = 1, b = 1;                     // dp[i-2], dp[i-1]
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}
// সময় O(n), space O(1)

এটি Fibonacci ক্রম। শুধু শেষ দুটি মান লাগে, তাই table-এর বদলে দুটি variable।

Top-down (memoization) বনাম bottom-up (tabulation)

Top-down: স্বাভাবিক recursion লিখুন, তারপর ফল cache করুন।

function climb(n, memo = {}) {
  if (n <= 1) return 1;
  if (memo[n]) return memo[n];
  return (memo[n] = climb(n - 1, memo) + climb(n - 2, memo));
}

• লেখা সহজ, শুধু দরকারি state হিসাব করে।
• Recursion গভীরতা ব্যবহার করে, বিশাল n-এ overflow হতে পারে।

Bottom-up: ক্ষুদ্রতম state থেকে ওপরের দিকে table ভরুন।

• Recursion নেই, সাধারণত দ্রুত এবং space অপ্টিমাইজ সহজ।
• সঠিক ভরার ক্রম আপনাকেই ঠিক করতে হয়।

উদাহরণ ২: coin change (ন্যূনতম coin)

Coin-এর মান ও একটি পরিমাণ দেওয়া, পরিমাণ বানাতে সবচেয়ে কম coin খুঁজুন, না পারলে -1।

• State: dp[a] = পরিমাণ a বানাতে সর্বনিম্ন coin।
• Recurrence: যেসব coin আঁটে তাদের ওপর dp[a] = 1 + min(dp[a - coin])।
• Base: dp[0] = 0; বাকিগুলো অসীম দিয়ে শুরু।

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
// সময় O(amount * coins), space O(amount)

Greedy পদ্ধতি (সবসময় সবচেয়ে বড় coin নেওয়া) কিছু coin সেটে ব্যর্থ হতে পারে, তাই DP লাগে।

উদাহরণ ৩: 0/1 knapsack

প্রতিটি item-এর ওজন ও মান আছে। ওজন সীমার মধ্যে মান সর্বোচ্চ করতে item বাছুন, প্রতিটি সর্বোচ্চ একবার।

• State: dp[i][w] = প্রথম i টি item দিয়ে ধারণক্ষমতা w-এ সেরা মান।
• Recurrence: item বাদ দিন, বা আঁটলে নিন: dp[i][w] = max(dp[i-1][w], value + dp[i-1][w - weight])।

function knapsack(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = capacity; w >= weights[i]; w--) {          // নিচের দিকে যান যাতে প্রতিটি item একবার ব্যবহৃত হয়
      dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
    }
  }
  return dp[capacity];
}
// সময় O(n * capacity), space O(capacity)

1D রূপে item দুবার ব্যবহার এড়াতে ধারণক্ষমতা নিচের দিকে loop করুন। ওপরের দিকে loop করলে unbounded knapsack হয়।

সাধারণ DP পরিবার

• 1D ক্রম: climbing stairs, house robber, maximum subarray, decode ways, longest increasing subsequence।
• Grid: unique paths, minimum path sum।
• দুটি string: longest common subsequence, edit distance।
• Knapsack-ধাঁচ: subset sum, partition equal subset, coin change।
• Interval ও partition: palindromic substring, matrix chain (কঠিনতর)।

উদাহরণ প্যাটার্ন: দুটি string (edit distance ধারণা)

State dp[i][j] হলো A-এর প্রথম i ও B-এর প্রথম j অক্ষরের উত্তর। Recurrence শেষ অক্ষরগুলো দেখে: সমান হলে dp[i-1][j-1] বহন করুন; নইলে insert, delete বা replace-এর সেরাটি নিয়ে এক যোগ করুন।

Interview-এর টিপ

• Brute-force recursion দিয়ে শুরু করুন, তার complexity বলুন, তারপর বলুন "একই উপসমস্যা পুনরাবৃত্ত হয়, তাই cache করব"।
• State-এর অর্থ জোরে বলুন। বেশিরভাগ ভুল অস্পষ্ট state থেকে।
• Recurrence যাচাই করতে হাতে ছোট table আঁকুন।
• সঠিক সমাধানের পর space অপ্টিমাইজ উল্লেখ করুন।
• DP না দেখলে greedy বা sorting সরলতর উত্তর দেয় কি না জিজ্ঞেস করুন।

সাধারণ ভুল

• পরের ধাপ ঠিক করার মতো যথেষ্ট তথ্য না ধরা state।
• ভুল base case বা off-by-one index।
• ভুল loop ক্রম (বিশেষত knapsack-এ)।
• state-এর সংখ্যা অতি বড় হলেও DP ব্যবহার।
• Memoization key-তে সব পরিবর্তনশীল parameter থাকা দরকার ভুলে যাওয়া।

অনুশীলনের সমস্যা

Climbing Stairs, House Robber, Maximum Subarray, Coin Change, Longest Increasing Subsequence, Unique Paths, Longest Common Subsequence, Partition Equal Subset Sum, Edit Distance।

মূল কথা: state ঠিক করুন, recurrence লিখুন, base case সেট করুন এবং cache বা tabulate করুন। Recursive সমাধান দিয়ে শুরু করে তারপর অপ্টিমাইজ করুন।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ২ (data structure ও আচরণ): 4 নম্বর (মোট 5)। আগের লেখা: Graph, BFS ও DFS: graph interview সমস্যা সমাধান.