整数拆分（普通母函数的应用）HDU1028

试题链接：HDU1028：https://vjudge.net/problem/HDU-1028

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
//解体思路：基本母函数的题，无限个1，2，3～～n可以用，问a[n]有多少种组成方式
int a[2005],b[2005];
int n;
void init()
{
    for (int i=0;i<=n;i++)
    {
        a[i]=0;
        b[i]=0;
    }
    a[0]=1;
}
int main()
{


    while(cin >> n)
    {
        init();//初始化
        for (int i=1;i<=n;i++) //一共n个变量（无限个1，2，3，～～n ）
        {
            for (int j=0;j<=n;j++)
            {
                for (int k=0;k+j<=n;k+=i) //k是新增多项式的指数，从k=0,i,2i,3i~~，需要注意的是这些多项式的系数都是1
                {
                    b[k+j]+=a[j]; //因为新增多项式的系数都是1，所以暂时储存的数组b，直接加a[j]就可以了
                }
            }
            for (int j=0;j<=n;j++)
            {
                a[j]=b[j];
                b[j]=0;
            }
        }
        cout << a[n] << endl;
    }
    return 0;
}