solution

此题有两种解法。

第一种解法就是裸的完全背包。

就相当于有n种物品，第i种物品的重量是i。每种物品有无限多个，问恰好填满一个容量为n的背包的方案数。

第二种解法是生成函数。

用生成函数表示拆分出的的数量。用表示拆分出的的数量。剩下的同理。最终的系数就是答案。

code

解法1

/*
* @Author: wxyww
* @Date:   2020-04-16 14:18:39
* @Last Modified time: 2020-04-16 14:19:55
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;

ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int f[150];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        memset(f,0,sizeof(f));
        f[0] = 1;
        for(int i = 1;i <= n;++i) {
            for(int j = i;j <= n;++j) 
                f[j] += f[j - i];
        }
        cout<<f[n]<<endl;
    }

    return 0;
}

解法2

/*
* @Author: wxyww
* @Date:   2020-04-16 14:11:40
* @Last Modified time: 2020-04-16 14:19:27
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 150;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int f[N][N],tmp[N];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        memset(f,0,sizeof(f));
        for(int i = 0;i <= n;++i) f[1][i] = 1;
        for(int t = 2;t <= n;++t) {
            for(int i = 0;i <= n;++i) {
                for(int k = 0;k + i <= n;k += t) {
                    f[t][i + k] += f[t - 1][i];
                }
            }
        }
        cout<<f[n][n]<<endl;
    }

    return 0;
}