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

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

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

输入格式

共一行,包含一个整数 n

输出格式

共一行,包含一个整数,表示总划分数量。

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

数据范围

1 ≤ n ≤ 1000

输入样例:

5

输出样例:

7

代码实现

#include <iostream>
using namespace std;
const int N = 1e3 + 10, MOD = 1e9 + 7;

int n, dp[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    dp[0] = 1;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            dp[j] = (dp[j] + dp[j - i])
    cout << dp[n];
    return 0;
} 
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status