题目描述

一个正整数n可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数n的一种划分。

现在给定一个正整数n，请你求出n共有多少种不同的划分方法。

输入格式
共一行，包含一个整数n。

输出格式
共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对10^9+7取模。

数据范围
1≤n≤1000

输入样例

5

输出样例

7

完全背包解法

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;

typedef long long LL;
const int N = 1010,M=1e9+7;
int s[N];//前缀和
int f[N];
int n;

//f[i][j]表示只从i-1中选,并且总和等于j的方案
//状态转移方程1:f[i][j]=f[i-1][j]+f[i][j-i]
//状态转移方程2:f[j]=f[j]+f[j-i]

int main()
{
    cin >> n;
    f[0] = 1;//一个数都不选,总和是0,算一种方案

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            f[j] = (f[j] + f[j - i]) % M;

    printf("%d", f[n]);
    return 0;
}

其他解法

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;

typedef long long LL;
const int N = 1010,M=1e9+7;
int f[N][N];
int n;

//f[i][j]表示所有总和是i,并且恰好表示成j个数的方案
//分成最小值是1,最小值大于1两组
//第二组计算时对每一个数减去1
//状态转移方程:f[i][j]=f[i-1][j-1]+f[i-j][j]

int main()
{
    cin >> n;
    f[0][0] = 1;//一个数都不选,总和是0,算一种方案

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = (f[i-1][j-1] + f[i-j][j]) % M;

    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum = (sum + f[n][i]) % M;

    printf("%d",sum);
    return 0;
}