在C ++中将计算完美平方数的程序加起来形成一个数
假设我们有一个正数n，我们必须找到和n相等的最小平方数。因此，如果数字为10，则输出为2，因为数字为10=9+1。
为了解决这个问题，我们将遵循以下步骤-
创建一个用于动态编程的表，其长度为n+1，并用无穷大填充
dp[0]：=0
对于i：=1，当i*i<=n
dp[j]：=dp[j]和1+dp[j–x]的最小值
x=我*我
对于j：=x到n
返回dp[n]
让我们看下面的实现以更好地理解-
示例
#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