Dynamic Programming: Fill the Table

বড় সমস্যা সমাধানের আগে তার ছোট ছোট version সমাধান করুন এবং উত্তরগুলো একটি table-এ লিখে রাখুন।

মূল ধারণা (একই homework বারবার করবেন না)

ধরুন আপনাকে জিজ্ঞেস করা হলো, "একবারে 1 বা 2 ধাপ করে উঠলে 30টি সিঁড়ি কত উপায়ে ওঠা যায়?" শুরু থেকে আবার গুনতে না গিয়ে খেয়াল করুন: 30 নম্বর সিঁড়িতে দাঁড়াতে হলে আপনি এসেছেন 29 বা 28 নম্বর সিঁড়ি থেকে। তাই ways(30) = ways(29) + ways(28)। প্রতিটি উত্তর প্রথমবার বের করেই table-এ লিখে রাখলে, পরের প্রতিটি cell হলো আগে থেকে থাকা cell গুলোর একটা দ্রুত look-up মাত্র।

প্রতিটি DP problem-এর recipe একই:

  1. State: একটি cell-এর মানে কী? (যেমন "dp[i] = i সংখ্যক সিঁড়ি ওঠার উপায়")।
  2. Base case: যে cell গুলোর মান না ভেবেই জানা।
  3. Transition: আগের cell থেকে একটি cell বানানোর formula। ছবিতে হলুদ cell গুলোই হলো সেই cell, যেগুলো formula পড়ে।
  4. Order: এমনভাবে fill করুন যাতে প্রয়োজনীয় cell গুলো সবসময় আগে থেকেই তৈরি থাকে।
  5. Answer: সাধারণত শেষ cell।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: কাজ cell-এর সংখ্যার সমান, প্রতিটি cell fill হয় constant সময়ে। Stairs: O(n)। LCS: O(m × n)। Knapsack: O(items × capacity)। table ছাড়া একই recursion exponential হারে ধীর হতে পারে।