C ++中的完美方块

假设我们有一个正整数n，求和的总和为n的最小平方数最少。因此，如果数字为13，则输出为2，因为数字为13 = 9 + 4

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

• 创建一个用于动态编程的表，其长度为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 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