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