DP版题解

直接上代码

#include<bits/stdc++.h>
using namespace std;
int n;
int dp[100005];
int main(){
    cin>>n;
    dp[0]=0;//0不需要任何平方数
    for(int i=1;i<=100005;i++){
        dp[i]=100005;//初始化dp数组，初始值设为较大数
    }
    //遍历1~n每个数求最小拆分数量
    for(int i=1;i<=n;i++){
        //枚举小于等于i的所有完全平方数j*j
        for(int j=1;j*j<=i;j++){
            dp[i]=min(dp[i],dp[i-j*j]+1);//状态转移：去掉一个平方数+1
        }
    }
    cout<<dp[n]<<"\n";
    return 0;
}