在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