ডাইনামিক প্রোগ্রামিং Digit DP
অনেকদিন ধরেই লিখব লিখব করে অবশেষে চলেই এলাম খুব মজার একটা টপিক নিয়ে যার নাম – Digit DP
ডিজিট ডিপির যেকোন প্রব্লেম সলভ করার আগে কয়েকটা বিষয় মাথায় রাখতে হবে…
১) কোন একটা সংখ্যার প্রতিটা পজিশনে কোন কোন digit বসতে পারে, সেটা বসালে সংখ্যার অবস্থাটা কেমন হবে, পরবর্তী স্টেট কেমন হবে, মূল এন্সারে তার কি কি প্রভাব পড়বে, সেগুলো মাথায় রাখতে হবে। সংখ্যার প্রতিটা পজিশন নিয়ে সহজে কাজ করার জন্য সেই সংখ্যার প্রতিটা ডিজিটকে কোন একটা integer array কিংবা string হিসেবে স্টোর করে রাখতে পারো।
২) সাধারণত ডিজিট ডিপি প্রব্লেমে কোন একটা রেঞ্জের মধ্যে কতগুলো সংখ্যার একটা নির্দিষ্ট প্রোপার্টি আছে, সেটা বের করতে বলা হয়। যেমন ধরো, ৫১০ থেকে ৯১৩১৫ এর মধ্যে কতগুলো সংখ্যায় অন্তত একটা শুন্য আছে, সেটা বের করতে বলা হল। ৫১০,৫২০,৫৩০……৬০০,৬০১ এরা এরকম কয়েকটা সংখ্যা।
এক্ষেত্রে রেঞ্জের মধ্যে সংখ্যাগুলো বের করার চেয়ে ০ থেকে ওই সংখ্যা পর্যন্ত সংখ্যাগুলো বের করার চিন্তা করলে সল্যুশনে পৌঁছাতে ও কোড করতে সহজ হবে। অর্থাৎ 0কে ৯১৩১৫ পর্যন্ত কতগুলো সংখ্যা আছে বের করো, এরপর সেটা থেকে ০ থেকে ৫০৯ পর্যন্ত কতগুলো সংখ্যা আছে সেটা বিয়োগ দাও, তাহলেই কিন্তু সহজেই ৫১০ থেকে ৯১৩১৫ পর্যন্ত কতগুলো সংখ্যা আছে সেটা বের হয়ে গেল!
অর্থাৎ আমাদের প্রব্লেমটা এবার অনেক সহজ হয়ে গেল। আমাদের কাজ হচ্ছে, কোন একটা নির্দিষ্ট প্রোপার্টির জন্যে ০ থেকে কোন একটা সংখ্যা পর্যন্ত কতগুলো সংখ্যা আছে, সেটা বের করা!
৩) এবার দেখি, কোন একটা পজিশনে কোন কোন ডিজিট বসতে পারে। ডিজিট বসানোর সময় মাথায় রাখতে হবে, সংখ্যাটা যেন কোনভাবেই ওই রেঞ্জের বাইরে চলে না যায়। একটা উদাহরণ দিলে সহজ হবে!
57035 (৫৭০৩৫)
এই সংখ্যার প্রথমে আছে ৫, একটু ভাবো তো এখানে আমরা কি কি ডিজিট বসাতে পারব?!
০-৫ সবগুলো ডিজিটই বসাতে পারব। ৬ কি বসাতে পারব?! না, কারণ ৬ বসালে পরের সবগুলো ০ বসালেও সেটা আমাদের সংখ্যার থেকে বড় হয়ে যাবে, অর্থাৎ রেঞ্জের বাইরে চলে যাবে।
৬০০০০ > ৫৭০৩৫
প্রথমে একদম Trivial কেসের কথা ভাবি, ৫ বসাই প্রথম পজিশনে, তাহলে পরের পজিশনে ৭ এর থেকে বেশি কিছু বসাতে পারব না, তাই তো?!
হ্যা, ৫৮০০০ > ৫৭০৩৫, তাই ৭ এর থেকে বেশি কিছু বসাতে পারব না।
তাহলে তো সহজ হয়েই গেল! প্রতিটা পজিশনে যেই ডিজিট আছে, তার থেকে ছোট ডিজিটগুলো বসাতে পারব, তাই তো?! না, ব্যাপারটা এতটাও সহজ না।
এবার প্রথম পজিশনে ৫ এর থেকে ছোট যেকোন সংখ্যা বসিয়ে, ধরলাম ৩. এবার, পরের পজিশনে কি কি সংখ্যা ৭পর্যন্ত তো বসাতেই পারবে – ৮,৯ কি বসানো যায়?
হ্যা, বসানো যায়,৩ এর পর সবগুলো ৯ , তাহলেও সংখ্যাটা ৫৭০৩৫ এর থেকে ছোট হচ্ছে।
৩৯৯৯৯ < ৫৭০৩৫
যদি কোন পজিশনে সেই ডিজিটের থেকে ছোট কোন ডিজিট থাকে তাহলে পরবর্তী যেকোন পজিশনে যেই ডিজিটই ছোট সংখ্যাই হবে।
প্রথম পজিশনে ৫ বসিয়ে ২য় পজিশনে আবার ৫ বসালে, তাহলে পরের সবগুলো পজিশনে সর্বোচ্চ ৯ বস সংখ্যাটা ছোটই থাকছে।
৫৫৯৯৯ < ৫৭০৩৫
এটাই ডিজিট ডিপির মূল রহস্য! প্রতিটা পজিশনে কিছু ডিজিট বসাতে হবে। আরেকটা স্টেটে রেখে দিবে হবে, ডিজিটটা বসানোর পর সংখ্যাটা মূল সংখ্যার থেকে ছোট হয়ে গেল কিনা! যদি ছোট হয়ে যায়, তবে পরের পজিশনগুলোতে যেকোন সংখ্যা বসানো। আর যদি এখনও সমান থাকে, তবে পরবর্তী পজিশনে যেই ডিজিট আছে, সেই ডিজিট ও তার ছোট ডিজিটগুলো বসবে।
লেখক
=====================
সোমা রানী দাস
বিভাগীয় প্রধান