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