ধরুন আমাদের একটি ধনাত্মক সংখ্যা n আছে, আমাদের সর্বনিম্ন সংখ্যক নিখুঁত বর্গ সংখ্যা বের করতে হবে যার যোগফল n এর সমান। তাই যদি সংখ্যাটি 10 হয়, তাহলে আউটপুট হবে 2, যেমন সংখ্যা 10 =9 + 1।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- ডাইনামিক প্রোগ্রামিংয়ের জন্য n + 1 দৈর্ঘ্যের একটি টেবিল তৈরি করুন এবং এটিকে অসীম দিয়ে পূরণ করুন
- dp[0] :=0
- এর জন্য i :=1, যখন i*i <=n
- x =i * i
- j এর জন্য :=x থেকে n
- dp[j] :=ন্যূনতম dp[j] এবং 1 + dp[j – x]
- রিটার্ন dp[n]
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
class Solution {
public:
int solve(int n) {
vector < int > dp(n+1,INF);
dp[0] = 0;
for(int i =1;i*i<=n;i++){
int x = i*i;
for(int j = x;j<=n;j++){
dp[j] = min(dp[j],1+dp[j-x]);
}
}
return dp[n];
}
};
main(){
Solution ob;
cout << ob.solve(10);
} ইনপুট
10
আউটপুট
2
