একটি ধনাত্মক পূর্ণসংখ্যা n দেওয়া আছে। n কে পূর্ণবর্গ সংখ্যাগুলোর যোগফল হিসেবে প্রকাশ করতে হবে এমনভাবে যেন ব্যবহৃত পূর্ণবর্গ সংখ্যাগুলোর সংখ্যা ন্যূনতম হয়।
উদাহরণ
n = 13 → আউটপুট: ২ (কারণ 13 = 9 + 4)
n = 147 → আউটপুট: ৩
ডাইনামিক প্রোগ্রামিং সমাধান
- সাইজ n+1-এর একটি DP টেবিল তৈরি করুন এবং Infinity দিয়ে ফিল করুন
- dp[0] = 0
- i = 1 থেকে √n পর্যন্ত লুপ চালান:
- x = i²
- j = x থেকে n পর্যন্ত: dp[j] = min(dp[j], 1 + dp[j - x])
- dp[n] ফেরত দিন
C++ প্রোগ্রাম উদাহরণ
#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];
}
};
int main() {
Solution ob;
cout << ob.numSquares(147);
return 0;
}
ইনপুট / আউটপুট
Input: 147 Output: 3
