मान लीजिए कि हमारे पास एक धनात्मक पूर्णांक n है, तो उन पूर्ण वर्ग संख्याओं की न्यूनतम संख्या ज्ञात कीजिए जिनका योग n है। तो अगर संख्या 13 है, तो आउटपुट 2 है, क्योंकि संख्याएं 13 =9 + 4 हैं
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- गतिशील प्रोग्रामिंग के लिए n + 1 लंबाई की एक तालिका बनाएं, और इसे अनंत से भरें
- dp[0] :=0
- i :=1 के लिए, जब i*i <=n
- x =मैं * मैं
- जे के लिए:=x से n
- dp[j] :=न्यूनतम dp[j] और 1 + dp[j - x]
- रिटर्न डीपी[एन]
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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