数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中的平方根
假设我们有一个正整数 n，找到和为 n 的最少完美平方数。因此，如果该数为 13，则输出为 2，因为数字为 13 = 9 + 4
为了解决这个问题，我们将遵循以下步骤 -
- 创建一个动态规划表，长度为 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 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
更新日期： 04-May-2020
440 次浏览
广告