মডিউল ১৭_১ঃ ডাইনামিক প্রোগ্রামিং কি?

আমরা এখন জানার চেষ্টা করবো ডাইনামিক প্রোগামিং কি। এই জিনিস এর অনেক থিওরিটিকাল আলাপ আলোচনা আছে। আমরা জিনিসটাকে একটু সহজ ভাবে বোঝার চেষ্টা করবো। ডাইনামিক প্রোগামিং বা সংক্ষেপে ডিপি হলো অপ্টিমাইজড রিকারশান। আমরা রিকারশান সম্পর্কে জানি। রিকারশান হচ্ছে এমন একটা জিনিস যেখানে আমাদের কাছে অনেক বড় একটা প্রবলেম থাকে যেটার ছোট একটা অংশ আমরা সলভ করি আর বাকি অংশটা ফাংশনকে দিয়ে সলভ করিয়ে নেই। ডিপি তে আমরা সেইম কাজটাই করবো তবে আমরা এইবার memoization নামক একটা পদ্ধতি অনুসরণ করে রিপিটেড কাজকে avoid করবো।

একটা উদাহরণ এর মাধ্যমে বোঝার চেষ্টা করি।

ধরি একটা রিকারসিভ ফাংশন আছেঃ

// Some code
function fn(n) {
  if(n < 0) return 1;
  return fn(n-1)+fn(n-2)
}

এখানে আমরা যদি রিকারশান ট্রি টা খেয়াল করে দেখি তাহলে দেখবো বেশ কিছু অপারেশন এখানে পুনরায় রিপিট হচ্ছে। যেগুলোকে আমরা এক একটা সাব প্রবলেম বলতে পারি।

এখন আমরা যদি সাবপ্রবলেম ১ যখন ক্যালকুলেট করেছি তখন এই যদি সেটা কোথাও স্টোর করে রাখতে পারতাম তাহলে আমাদের সাবপ্রবলেম ২ কে আর আলাদাভাবে হিসেব করতে হতো না। এই পদ্ধতির নাম হচ্ছে memoization পদ্ধতি।

এইভাবে রিকারশানকে অপ্টিমাইজ করার পদ্ধতিকে আমরা ডাইনামিক প্রোগামিং বলে থাকি।

ডিপি এর দুইটা এপ্রোচ বিদ্যমান।

১। Memoization method(Recursive)

২। Tabulation method(Iterative)