पूर्ण वर्गों की संख्या गिनने के लिए प्रोग्राम को C++ में एक संख्या बनाने के लिए जोड़ा जाता है

मान लीजिए कि हमारे पास एक धनात्मक संख्या n है, हमें उन पूर्ण वर्ग संख्याओं की सबसे छोटी संख्या ज्ञात करनी है जिनका योग n के समान है। तो अगर संख्या 10 है, तो आउटपुट 2 है, क्योंकि संख्याएँ 10 =9 + 1 हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• गतिशील प्रोग्रामिंग के लिए 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 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