मान लीजिए हमारे पास एक धनात्मक संख्या 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