题目描述

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

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

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

输入格式

共一行，包含一个整数n。

输出格式

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

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

数据范围

1≤n≤1000

输入样例:

5

输出样例：

7

主要考点

动态规划

C ++ 代码1

解题思路

完全背包思想

闫氏DP分析法

一、状态表示：f[i][j]
1. 集合：所有从1 ~ i中选,总和为j的所有方案.
2. 属性：最小值

二、状态计算：
1. 思想-----集合的划分
2. 集合划分依据：根据最后一步i选几个进行划分
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + f[i - 1]][j - 3 * i] + ···
f[i][j - i] = + f[i - 1][j - i] + f[i - 1][j - 2 * i] + f[i - 1]][j - 3 * i] + ···
因此,f[i][j] = f[i - 1][j] + f[i][j - 1]

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, MOD = 1e9 + 7;

int f[N];
int n;

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]) % MOD;
        }
    }
    cout << f[n] << endl;
    return 0;
}

C ++ 代码2

类似题

鸣人的影分身

解题思路

闫氏DP分析法

一、状态表示：f[i][j]
1. 集合：分为i个数且总和为j的所有方案.
2. 属性：最小值

二、状态计算：
1. 思想-----集合的划分
2. 集合划分依据：根据最小值进行划分,分为两类：
具体划分：
最小值 = 1： f[i - 1][j - 1]
最小值 > 1： f[i][j - i]
f[i][j] = f[i - 1][j - 1] + f[i][j - i]

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, MOD = 1e9 + 7;

int f[N][N];
int n;

int main(){
    cin >> n;

    f[0][0] = 1;
    for(int i = 1; i <= n; i ++){//分为i个数
        for(int j = i; j <= n; j ++){//枚举总和
            f[i][j] = (f[i - 1][j - 1] + f[i][j - i]) % MOD;
        }
    }

    int res = 0;
    for(int i = 1; i <= n; i ++) res = (res + f[i][n]) % MOD;
    cout << res << endl;

    return 0;
}