在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