首页 > 试题广场 >

最少的完全平方数

[编程题]最少的完全平方数
  • 热度指数：794 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个正整数n，请找出最少个数的完全平方数，使得这些完全平方数的和等于n。
完全平方指用一个整数乘以自己例如1*1，2*2，3*3等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。例如:1，4，9，和16都是完全平方数，但是2，3，5，8，11等等不是

数据范围:

示例1

输入

5

输出

2

说明

5=1+4
示例2

输入

8

输出

2

说明

8=4+4
示例3

输入

9

输出

1
算法知识视频讲解
添加回答
C
企鹅暴打皮卡丘头像 企鹅暴打皮卡丘
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 */
bool issquare(int n)
{
    if(n==1||n==4)
        return true;
    for(int i=1;i<n/2;i++)
    {
        if(i*i==n)
            return true;
        if(i*i>n)
            break;
    }
    return false;
}
int min(int a,int b)
{
    if(a<b)
    return a;
    return b;
}
int numSquares(int n ) {
    int dp[n+1];
    for(int i=0;i<=n;i++)
        dp[i]=1000;
    dp[1]=1;
    dp[2]=2;
    for(int i=2;i<=n;i++)
    {
        if(issquare(i))
            dp[i]=1;
        else
        {
            for(int j=1;j<i;j++)
            {
                dp[i]=min(dp[j]+dp[i-j],dp[i]);
            }
        }
    }
    return dp[n];
}
发表于 2022-09-27 16:36:44 回复(0)
提交观点

问题信息

动态规划
上传者：牛客301499号
难度：
1条回答 2715浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最少的完全平方数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号