এক আনমু কেমনে (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 কে তাড়াতাড়ি কিভাবে ছোট করা যাই এবং ছোট করতে করতে এক সময় ওয়ান(এক)  নিয়ে আসে । যদি তুমি ভাল করে দেখ তবে দেখবে গ্রিডি স্টেটেজিটা আসলে কাজ করতে নাহ । তোহ লোভী চিন্তা করলে এখানে চলবে নাহ। একটা উদাহরণ দেখা যাক : ধর দেয়া আছে n = 10 , Greedy --> 10 /2 = 5 -1 = 4 /2 =...