最少的完全平方数

C 解法, 执行用时: 3ms, 内存消耗: 336KB, 提交时间: 2022-03-12

#include <stdio.h>
#include <limits.h>
int main(){
    int mm = INT_MAX;
    int n;
    scanf("%d",&n);
     int i ,j;
    int dp[n];
    dp[0]=0;
    for(i=1;i<=n;i++){
        dp[i] = mm;
    }
    
    for(i=0;i<n;i++){
        for(j=1;i+j*j<=n;j++){
            if(dp[i]+1<dp[i+j*j]){
                dp[i+j*j]=dp[i]+1;
            }
        }
    }
    
    printf("%d",dp[n]);
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-05-26

#include <iostream>
#include <vector>
#include <set>
using namespace std;
bool check(int n, int count, set<int> & st);
int main() {
    int n;
    cin >> n;
    set<int> st;
    for (int i = 1, k = 1; (k = i * i) <= n; ++i) {
        st.insert(k);
    }
    int count = 1;
    while (count < 5) {
        if (check(n, count, st)) {
            cout << count << endl;
            break;
        }
        ++count;
    }
    return 0;
}
bool check(int n, int count, set<int> &st) {
    if (count == 1) return st.find(n) != st.end();
    for (auto it = st.begin(); it != st.end(); ++it) {
        if (check(n - *it, count - 1, st)) return true;
    }
    return false;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 440KB, 提交时间: 2022-03-13

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main(){
    int n;
    cin>>n;
    int dp[10100];
    for(int i=0;i<10010;i++)dp[i]=1e9;
    dp[0]=0;
    for(int i=1;i*i<=n;i++){
        for(int j=i*i;j<=n;j++){
            dp[j]=min(dp[j],dp[j-i*i]+1);
        }
    }
//     for(int i=0;i<=n;i++){
//         cout<<dp[i]<<endl;
//     }
    cout<<dp[n]<<endl;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 444KB, 提交时间: 2022-08-06

#include<iostream>
#include<vector>
#include<set>
using namespace std;
bool check(int n,int count,set<int> &st);
int main(){
	int n;
	cin>>n;
	set<int> st;
	for(int i=1,k=1;(k=i*i)<=n;++i)
	{
		st.insert(k);
	}
	int count=1;
	while(count<5)
	{
		if(check(n,count,st))
		{
			cout<<count<<endl;
			break;
		}
		++count;
	}
	return 0;
} 
bool check(int n,int count,set<int> &st)
{
	if(count==1)
	return st.find(n)!=st.end();
	for(auto it=st.begin();it!=st.end();++it)
	{
		if(check(n-*it,count-1,st))
		return true;
	 } 
	 return false;
}

C 解法, 执行用时: 4ms, 内存消耗: 300KB, 提交时间: 2022-06-14

#include <stdio.h>
#include <string.h>


/*
解题思路：
题目中的n等价于背包问题中的背包容量
1*1，2*2，3*3等表示物品种类
可以多次装入同一个物品，所以等价于完全背包问题中的恰好装满问题，因为求的是最少个数的完全平方数，初值应该设为很大的一个数值
所以背包问题循环中的第一个循环：物品数量范围1-i*i.i*i<=n
背包问题循环中的第二个循环，背包容量范围1-j,j<=n
当背包容量（完全平方数之和）小于i*i,不能装入该物品
当完全平方和j>i*i的时候，取dp[j] = min(dp[j],dp[j-i*i]+1);

*/
int min(int x, int y)
{
    return x<=y?x:y;
}

int main()
{
    int n;
    scanf("%d",&n);
    int dp[10001];
    for(int i=1; i<=n; i++)
    {
        dp[i] = 0x3f3f;
    }
    dp[0] = 0;//dp[i]表示完全平方数之和等于i的时候，最小的完全平方个数
    for(int i=1; i*i<=n; i++)//完全平方和种类数
    {
        for(int j=1; j<=n; j++)//j表示总和，不能大于n
        {
            if(j >= i*i)
            {
                dp[j] = min(dp[j],dp[j-i*i]+1);
            }
        }
    }
       printf("%d",dp[n]);
    return 0;
}

详情