আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি ধনাত্মক সংখ্যা নেয়, সংখ্যা বলুন, একমাত্র যুক্তি হিসাবে।
ফাংশনটি এমন নিখুঁত বর্গ সংখ্যার সংমিশ্রণ খুঁজে পাওয়া উচিত যা যোগ করার সময় ইনপুট হিসাবে প্রদত্ত সংখ্যাটি দেয়। আমাদের করতে হবে যে আমরা যতটা সম্ভব কম সংখ্যক নিখুঁত স্কোয়ার ব্যবহার করি।
যেমন −
যদি ইনপুট নম্বর হয় −
const num = 123;
তারপর আউটপুট −
হওয়া উচিতconst output = 3;
কারণ 123 =121 + 1 + 1
এটি একটি ক্লাসিক ডায়নামিক প্রোগ্রামিং সমস্যা যেখানে আমরা একটি নির্দিষ্ট সংখ্যার ফলাফলের পূর্ববর্তী সংখ্যার ফলাফলের উপর ভিত্তি করে পৌঁছাতে পারি৷
কোডে সরাসরি ঝাঁপিয়ে পড়ার আগে প্রথমে একটি সাধারণ প্যাটার্ন বোঝার চেষ্টা করা যাক এবং আসলে ডিপি কীভাবে সমাধানটি তৈরি করতে আমাদের সাহায্য করবে।
ছয় পাঁচটি সংখ্যার ফলাফল হবে −
1 --> 1 (1) 2 --> 2 (1 + 1) 3 --> 3 (1 + 1 + 1) 4 --> 1 (4) 5 --> 2 (4 + 1) 6 --> 3 (4 + 1 + 1)
এটি স্পষ্টভাবে দেখায় যে সফল ফলাফল পেতে আমাদের পূর্ববর্তী ফলাফলের সাথে সমন্বয় করার চেষ্টা করতে হবে।
উদাহরণ
নিম্নলিখিত কোড -
const num = 123;
const sumSquares = (num) => {
let arr = new Array(num + 1).fill(0);
arr[1] = 1;
for(let i = 1; i * i <= num; i++) {
for(let j = i * i; j < arr.length; j++) {
if(arr[j] == 0) {
arr[j] = arr[j - (i * i)] + 1;
} else {
arr[j] = Math.min(arr[j - (i * i)] + 1, arr[j]);
}
}
};
return arr[num];
};
console.log(sumSquares(num)); আউটপুট
নিম্নোক্ত কনসোল আউটপুট -
3
