题目描述
一个正整数 \(n\) 可以表示成若干个正整数之和，形如：\(n = n\_1 + n\_2 + … + n\_k\)，其中 $n_1 ≥ n_2 ≥ … n_k, k ≥ 1 $
我们将这样的一种表示称为正整数 \(n\) 的一种划分。
现在给定一个正整数 \(n\)，请你求出 \(n\) 共有多少种不同的划分方法。
输入格式
共一行，包含一个整数 \(n\)。
输出格式
共一行，包含一个整数，表示总划分数量。
由于答案可能很大，输出结果请对 \(10^9 + 7\) 取模。
数据范围
$ 1 ≤ n ≤ 1000 $
输入样例:
5
输出样例：
7
算法1
(DP:从1~i中选，且总和等于j) \(O(n^2logn)\)
f[i][j]:从1~i中选，且总和等于j,此时问题简化成完全背包问题
时间复杂度
dont know
空间复杂度
dont know
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int f[N];
int mod = 1e9 + 7;
int main()
{
cin >> n;
f[0] = 1;
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];
return 0;
}
算法2
(DP:总和为i，总个数为j)
f[i][j]:表示使用j个数能够凑成总和为i的方案的集合
-
使用
j个数能够凑成i，这j个数中最小值为1的集合，去掉一个1，则状态变为：f(i,j)=f(i−1,j−1) -
使用
j个数能够凑成i，这j个数中最小值不为1的集合，将这j个数都减去一个1，则状态变为：f(i,j)=f(i−j,j)此时状态表示为j个数能够凑成i-j的所有方案的数量。
时间复杂度
dont know
空间复杂度
dont know
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int f[N][N];
int mod = 1e9 + 7;
int main()
{
cin >> n;
// for(int i = 0; i <= n; i ++) f[0][i] = 1;
f[1][1] = 1;
for(int i = 2; i <= n; i ++)
for(int j = 1; j <= i; j ++)
f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
int res = 0;
for(int i = 1; i <= n; i ++) res = (res + f[n][i]) % mod;
cout << res;
return 0;
}