A+B+C+D（数字拆分统计情况）

解题思路:

采用暴力破解的方法将所有的可能试出来

注意事项:

1、当数字较大时所有的可能性也就比较多 int 可能不能完整的保存所有的可能性
2、当数据较多时每次递归计算的值可能被多次计算导致时间过长

    在这里通过申请数组将以经计算的过的情况保存下来，在下次遇到时可以直接引用，从而减少程序运行时间

参考代码:

单单只采用循环或者递归会因超时而不通过

循环

#include #include using namespace std;
long long f(int a)
{
    long long n=0;
    if(a<4)//要拆分的数值小于拆分的个数无法拆分为正整数，返回0
        return 0;
    else if(a==4)//要拆分的数为4时只有一种情况直接返回减少运行时间
    {
        return 1;
    }
    else
    {
        for(int i=1;i<a;i++)//拆出第一个数
        {
            for(int j=1;j<a-i;j++)//拆出第二个数
            {
                for(int k=1;k<a-i-j;k++)//拆出地三个数，同事第四个数也确定了
                {
                            n++;
                }
            }
        }
    }
    return n;
}
int main()
{
    int n;
    cin>>n;//表示要输入n个测试数值
    int a;
    vector  s(n);//用于储存输入的数值
    for(int i=0;i>s[i];    }
    for(int i=0;i<n;i++)//调用函数进行计算
    {
        a=s[i];
        cout<<f(a)<<endl;
    }
    return 0;
}

递归

#include #include using namespace std;
long long f(int a,int d)//a为要拆分的数值,d为要拆分为d个数
{
    if(d==1)//d=1时值是惟一的返回1并结束递归
        return 1;
    if(a<d)//要拆分的数值小于拆分的个数无法拆分为正整数，返回0
    {
        return 0;
    }
    else
    {
        long long n=0;//储存每次的计算结果
        d--;
        for(int i=1; i>n;//表示要输入n个测试数值
    int a;
    vector  s(n);//用于储存输入的数值
    for(int i=0; i>s[i];
    }
    for(int i=0; i<n; i++)//调用函数进行计算
    {
        a=s[i];
        cout<<f(a,4)<<endl;
    }
    return 0;
}

递归+数组保存

#include #include using namespace std;
long long cf[4][1001];//储存已经计算的情况
long long f(int a,int d)//a为要拆分的数值,d为要拆分为d个数
{
    if(d==1)//d=1时值是惟一的返回1并结束递归
        return 1;
    if(a<d)//要拆分的数值小于拆分的个数无法拆分为正整数返回0
    {
        return 0;
    }
    else if(cf[d-1][a]!=0)//查看之前是否计算过，计算过则直接使用该值
        return cf[d-1][a];
    else
    {
        long long n=0;//储存每次的计算结果
        d--;
        for(int i=1; i>n;//表示要输入n个测试数值
    int a;
    vector  s(n);//用于储存输入的数值
    for(int i=0; i>s[i];
    }
    for(int i=0; i<n; i++)//调用函数进行计算
    {
        a=s[i];
        cout<<f(a,4)<<endl;
    }
    return 0;
}