C++ में बिल्कुल सही वर्ग

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