Dynamic Programming

এক আনমু কেমনে (Minimum Steps to One)


ডাইনামিক প্রোগ্রামিং এর বেসিক খুব সুন্দর একটা প্রবলেম নিয়ে আলোচনা করবো এই প্রবলেমের টিউটোরিয়ালটা কোডশেফের ডাইনামিক প্রোগ্রামিং টিউটোরিয়াল সেকশন থেকে নেয়া । এই টিউটোরিয়াল পড়ার আগে রিকারশন, ডিপি উপর ধারনা থাকতে হবে রিকারশন বা ডিপি নিয়ে যদি কারও কোন প্রবলেম থাকে তোহ  ফাহিমভাইয়ের ব্লগ এবং শাফায়েতভাইয়ের ব্লগ অতুলনীয় সেখান থেকে দেখে নিতে পারো/পারেন
প্রবলেম স্টেটমেন্ট

একটি পজেটিব ইন্টিজার দেয়া থাকবে এবং কিছু শর্ত দেয়া থাকবে বের করতে হবে মিনিমাম কতগুলো স্টেপে সংখ্যাটিকে ওয়ান(এক) করা যাই । শর্তগুলো হল :
    ১. এক বিয়োগ করতে পারি (n=n-1) ।
    ২. যদি সংখ্যাটি ২ দ্বারা বিভাজ্য হয় তবে ২ দ্বারা ভাগ করা যাবে ।  
         ( if n % 2 == 0 , then n = n / 2  )
    ৩. যদি সংখ্যাটি ৩ দ্বারা বিভাজ্য হয় তবে ৩ দ্বারা ভাগ করা যাবে । 
         ( if n % 3 == 0 , then n = n /3  )

 উদাহরণ :     1.)  For n = 1 ,  output: 0      
                  2.) For n = 4 ,  output: 2  ( 4  /2 = 2  /2 = 1 )   
                  3.) For n = 7 ,  output: 3  (7  -1 = 6   /3 = 2   /2 = 1)
সল্ভিং ট্রিক্স
 
স্টেপগুলো বাছাই করার জন্য অনেকে গ্রিডি চিন্তা করে, তারা চিন্তা করে যে n কে তাড়াতাড়ি কিভাবে ছোট করা যাই এবং ছোট করতে করতে এক সময় ওয়ান(এক)  নিয়ে আসে । যদি তুমি ভাল করে দেখ তবে দেখবে গ্রিডি স্টেটেজিটা আসলে কাজ করতে নাহ । তোহ লোভী চিন্তা করলে এখানে চলবে নাহ। একটা উদাহরণ দেখা যাক :

 



তাহলে বুজতে পারছ যে আমাদের সব স্টেপ গুলো বের করে তার মধ্যে মিনিমাম স্টেপটা আমাদের রেজাল্ট । ছবিতে পুরা ট্রি টা দেই নি কারণ আমরা মিনিমাম স্টেপ পেয়ে গেছি ।

যদি আমরা রিকারশন দিয়ে শুরু করি
F(n) = 1 + min{ F(n1) , F(n/2) , F(n/3),} , if (n>1) else 0  ( i.e., F(1) = 0 ) 
তুমি রিকারশন ইকুয়েশন্টা পেয়ে গেছ এখন তুমি কোড করতে পারো তবে একটু খেয়াল করলে দেখবে যে কিছু অভারলেপিং আছে এই প্রবলেমে যেমন ৪ কেলকুলেট করা হয়েছে ৫ এর জন্য আবার ৮ কে ভেঙে আমরা ৪ পেয়েছি একি ভাবে ২ ও ৩ অভারলেপিং আছে এবং সামনে আরো আসতে পারে । তো ডাইনামিক প্রোগ্রামিং দ্বারা এটাকে আমারা মেমোইজেশন করে রাখতে পারি । ডিপি করা জন্য আমাদের স্টেট অ্যান্ড বেস কেস জানা দরকার তো এখানে বেস কেস হল n যখন ওয়ান(এক) হয়ে যাবে তখন রিটার্ন জির if(n==1)  return 0; আর n হল আমাদের স্টেট । তুমি সাবপ্রবলেমের রেজাল্ট মেমোইজেশন আকারে মনে/সেব রাখতে পার । কিভাবে রাখবে একটু দেখিয়ে দিচ্ছি :

Memoization

 

Bottom-Up DP

প্রবলেম :

Posted by Shipu Ahamed in Dynamic Programming, 0 comments