1. dp完全背包

#include <bits/stdc++.h>
using namespace std;
int m,dp[100005];
int main(){
    scanf("%d",&m);
    for(int i=1;i<=m;i++)dp[i]=INT_MAX;
    for(int i=1;i<=sqrt(sqrt(m));i++){
        int w=i*i*i*i;
        for(int j=w;j<=m;j++)dp[j]=min(dp[j-w]+1,dp[j]);
    }
    cout<<dp[m];
    return 0;
}

2. bfs广搜

#include <bits/stdc++.h>
using namespace std;
int m,step[100005];
bool vis[100005];
int bfs(int x){
    queue<int>q;
    q.push(x);
    vis[x]=1;
    while(q.size()){
        int f=q.front();
        q.pop();
        if(f==0)return step[0];
        for(int i=1;i<=sqrt(sqrt(f));i++){
            int tx=f-i*i*i*i;
            if(!vis[tx]){
                q.push(tx);
                vis[tx]=1;
                step[tx]=step[f]+1;
            }
        }
    }
    return step[0];
}
int main(){
    scanf("%d",&m);
    printf("%d",bfs(m));
    return 0;
}