ধরুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যা n আছে, নিখুঁত বর্গ সংখ্যার সর্বনিম্ন সংখ্যা বের করুন যার যোগফল n। সুতরাং যদি সংখ্যাটি 13 হয়, তাহলে আউটপুট 2 হবে, যেমন সংখ্যা 13 =9 + 4
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- ডাইনামিক প্রোগ্রামিংয়ের জন্য 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 numSquares(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.numSquares(147));
} ইনপুট
147
আউটপুট
3
