用 C++ 编写一个程序来计算完美平方数相加得到一个数

假设我们有一个正数 n，那么我们必须找到完美平方数之和与 n 相同的最少数量。所以如果这个数是 10，那么输出是 2，因为这些数字为 10 = 9 + 1。

为了解决这个问题，我们将遵循以下步骤 -

• 创建一个长度为 n + 1 的动态规划表格，并用无穷大填充
• dp[0] := 0
• 当 i := 1，且 i*i <= n 时
  • x = i * i
  • 当 j := x 到 n 时
    • dp[j] := dp[j] 和 1 + dp[j – x] 的最小值
• 返回 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

Arnab Chakraborty

更新于： 2020 年 10 月 20 日

78 次浏览

开启你的职业生涯

完成课程获得认证

开始