题目描述
一个正整数n可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数n的一种划分。
现在给定一个正整数n,请你求出n共有多少种不同的划分方法。
输入格式
共一行,包含一个整数n。
输出格式
共一行,包含一个整数,表示总划分数量。
由于答案可能很大,输出结果请对109+7取模。
数据范围
1≤n≤1000
样例
输入样例:
5
输出样例:
7
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N=1e3+10,mod = 1e9+7;
//f[i][j]从前i个数中选,总和为j的划分方法
int f[N][N];
int main(){
int n;scanf("%d",&n);
//前i个数总和是0:f[i][0] = 1 (即只有1中方案,就是1个都不选)
for(int i=0;i<=n;i++) f[i][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=0;k*i <= j;k++) f[i][j]=(f[i][j]+f[i-1][j - k*i])%mod;
}
}
printf("%d",f[n][n]);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N=1e3+10,mod = 1e9+7;
//f[i][j]从前i个数中选,总和为j的划分方法
/**
* f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j-2*i] + …… + f[i-1][j-s*i]
* f[i][j-i] = f[i-1][j-i] + f[i-1][j-2*i] + …… + f[i-1][j-s*i]
* */
int f[N][N];
int main(){
int n;scanf("%d",&n);
//前i个数总和是0:f[i][0] = 1 (即只有1中方案,就是1个都不选)
for(int i=0;i<=n;i++) f[i][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(j >= i) f[i][j]=(f[i-1][j]+f[i][j-i])%mod;
else f[i][j]=f[i-1][j];
}
}
printf("%d",f[n][n]);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N=1e3+10,mod = 1e9+7;
/**
* dp的方程不一定是唯一的,不同的思路可以得出不同的方程
* */
/**
* f[i][j] : 表示组成总和为i的j个数的所有方案
*
* 属性 : 数量
*
* 划分:
* 最小值等于1 f[i][j] = f[i - 1][j-1]
*
* 最小值大于1 f[i][j] = f[ i - j ][j]
* 则: f[i][j] = f[i-1][j - 1] + f[i-j][j]
* */
int f[N][N];
int main(){
int n;scanf("%d",&n);
f[0][0]=1;
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])%mod;
}
}
int res=0;
for(int i=1;i<=n;i++) res = (res+f[n][i])%mod;
printf("%d",res);
return 0;
}