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
热门推荐
3 祝福语简短的微信
10 幼儿祝福语大全简短贺卡
11 感谢教官文案祝福语简短
12 鼠年同事祝福语简短创意
13 元旦祝福语 简短独特群发
14 妈咪跟我生日祝福语简短
15 给儿子新婚祝福语简短
16 伴娘祝福语长文案简短
17 恭喜高考完祝福语简短
18 生日祝福语送老公简短