求解acm题目，一直时间超限，求更优的算法

Question

 #include<cstdio>
#include<cstring>
int v[10000];
int a[10000];
int s;

int check(int k)
{
    for(int i=0;i<s;i++)
        if(k == a[i])
            return 0;
    return 1;
}

void dfs(int t,int n,int k)
{
    if(n==0){
        if(check(k)){
            a[s++] = k;
            //for(int i=0;i<k;i++)
                //printf("%d ",v[i]);
            //printf("\n");
        }
        return ;
    }
    for(int i=t;i>=1;i--){
        if( n>=i*i*i){
            //v[i] = 1;
            v[k] = i;
            dfs(t,n-i*i*i,k+1);
            //v[i] = 0;
            v[k] = 0;
        }
    }
}

int main()
{
    int n;
    int t;
    int flag;
    while(~scanf("%d",&n)){

    s = 0;
    flag = 0;
    memset(v,0,sizeof(v));
    memset(a,0,sizeof(a));
    for(int i=1;;i++){
        if(i*i*i>=n){
            if(i*i*i==n)
                flag = 1;
            t = i;
            break;
        }
    }
    if(!flag)
        t = t - 1;
    //printf("t=%d\n",t);
    dfs(t,n,0);
    //for(int i=0;i<s;i++)
        //printf("%d ",a[i]);
    //printf("\n");
    printf("%d\n",s);
    //n++;
    }
    return 0;
}

Answer 1

这个题目要用动态规划，不知道你怎么写的，应该先算出1~N（N^3<=n）的立方和
然后再对它们排列组合。