首页 > 试题广场 >

最少的完全平方数

[编程题]最少的完全平方数
  • 热度指数：853 时间限制：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
算法知识视频讲解
添加回答
Java
牛客499848474号头像 牛客499848474号 
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int numSquares (int n) {
        // write code here
        //↓14-18行可有可无
        for (int i = 1; i < n / 2; i++) {
            if (n == i * i) {
                return 1;
            }
        }

        int[] M = new int[n + 1];
        // M[i] represents the minimum number of boxes to pack num swags up
        // initialize
        M[1] = 1;
        for (int i = 2; i <= n; i++) {
            M[i] = i;
            for (int j = 1; j * j <= i; j++) {
                M[i] = Math.min(M[i - j * j] + 1, M[i]);
            }
        }
        return M[n];
    }
}


发表于 2025-01-02 13:01:48 回复(0)
Rust
老刘001头像 老刘001 
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param n int整型 
        * @return int整型
    */
    pub fn numSquares(&self, n: i32) -> i32 {
        // write code here
        let mut res = vec![0];
        for i in 1 ..= n {
            res.push(i);
            for j in 1 ..= i {
                if j * j <= i {
                    use std::cmp::min;
                    res[i as usize] = min(res[i as usize], res[(i - j * j) as usize] + 1);
                } else {
                    break;
                }
            }
        }
        res[n as usize]
    }
}

发表于 2023-09-09 23:15:54 回复(0)
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)
牛娃牛娃头像 牛娃牛娃 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int numSquares(int n) {
        // write code here
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i =1;i*i<=n;i++){
            for(int j =1;j<=n;j++){
                if(j-i*i>=0){
                    dp[j] =min(dp[j-i*i]+1,dp[j]);
                }
            }
        }
        return dp[n];
    }
};

发表于 2022-04-11 10:24:54 回复(0)
JavaScript Node
Jimmy0.0头像 Jimmy0.0
不知道为什么 JavaScript node环境下，牛客的解释器不能得到结果，我自己用vscode配合nodejs完全没问题，结果没错。
发表于 2022-01-23 18:32:51 回复(1)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

最少的完全平方数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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