题解 | 最少的完全平方数

#include <bits/stdc++.h>

//动态规划的思想用存储前面计算过的东西，加以利用
//完全平方数可以多次使用，类似完全背包，正好等于n的时候的用值最少
using namespace std;

#define N (int)(1e4+5)

int dp[N];
//体积为完全平方数的值
int volume[N];
//价值全部为1

int my_min(int a,int b){
    return (a<b)?a:b;
}

//正序
int main(){
    int n,v;
    scanf("%d",&n);
    v=(int)sqrt(n);
    for(int i=1;i<=v;i++){
        volume[i]=i*i;
    }
    for(int i=1;i<=n;i++)
    {
        dp[i]=INT_MAX;
    }
    for(int i=1;i<=v;i++)
    {
        for(int j=volume[i];j<=n;j++)
        {
            dp[j]=my_min(dp[j],dp[j-volume[i]]+1);
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}