给定一个正整数n，请找出最少个数的完全平方数，使得这些完全平方数的和等于n。
完全平方指用一个整数乘以自己例如1*1，2*2，3*3等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。例如:1，4，9，和16都是完全平方数，但是2，3，5，8，11等等不是
数据范围:
[编程题]最少的完全平方数
动态规划，JavaScript版本
思路：
对小于n的每一个数都计算出其最优的平方数个数，从1->n依次计算，并且依据之前的结果来计算当前最优的平方数个数，优先解决子问题并利用子问题结果计算最终结果。
JavaScript代码如下:
const numSquares = (n) => {
展开全文
bool check(int n){
return n == (int)sqrt(n) * sqrt(n);
}
int numSquares(int n) {
// write code here
vector<int> dp(n+1,INT_MAX);
展开全文
先把传入的数字开平方根，然后向下取整，这样就可以获取到一个最大的完全平方数
然后减去这个数的平方，直到传入的数字为0
这样就可以获取一组完全平方数
但是这样不一定是最少的
不过我们已经得到了最大的完全平方数，所以再用比这个小的数字依次用上面的逻辑得到多组数据，最后取最小的
提醒： 上面的操作在输入
展开全文
dp 问题, 设置 dp[i] 表示能组成 i 的最少完全平方数, dp[0] = 0, dp[i] = min(dp[i - j * j] + 1, dp[i]) j < i dp[i - j * j] 表示上一个组成完全平方数的最少值,因为每个正数都可以是完全平方数(1 + 1 + ...
展开全文
问题信息
通过挑战的用户
查看代码-
2022-09-16 17:01:40
-
2022-09-14 14:52:49 -
2022-09-11 14:36:15
-
2022-09-08 12:58:48
-
2022-09-07 15:34:34
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
