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