题目描述
一个正整数 n 可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n,请你求出 n 共有多少种不同的划分方法。
样例
5
算法1
f[i,j] 状态表示为 f[i-1][j-1]+f[i-j][j];i为总和值 j为数量
集合划分为最小值含有至少一个1 与最小值不含有1两种情况
如6=3+2+1 在前式限定最小值至少含有一个1的前提下 6=3+2+1的方案数与5=3+2的方案数相同
同理可知f[i][j]此集合中所有含有最小值1的集合都可以转换为f[i-1][j-1]
集合划分最小值大于1的情况
6=4+2,6=3+3 只可以划分这两个,6=4+2 方案可以由4=3+1这个方案中得来 6=3+3 可以由4=2+2这个式子得来 由于只是把每一个加数都加上1 所以方案数不变
f[i][j]集合中所有最小值大于1的集合都可以转化为f[i-j][j]这个集合来求解
可以写出状态转移表达式f[i,j]=f[i-1][j-1]+f[i-1][j]
初始状态表示为f[0][0]=1,一个数的值为零 并且由0个加数构成的方案为1
最后将f[n][1-n]加和得出当一个数值为n 由1个加数到n个加数构成的方案之和
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N=1010,M=1e9+7;
int f[N][N];
int main(){
int n;
cin>>n;
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j]=f[i-j][j]+f[i-1][j-1];
f[i][j]%=M;}
}
int res=0;
for(int i=1;i<=n;i++)
res=(res+f[n][i])%M;
cout<<res;
}
算法2
(完全背包问题转化)
f[i,j]i表示考虑了第几个加数i属于[1,n] j表示和
完全背包问题的思想 f[i][j]=f[i-1][j]+f[i-1][j-i]+f[i-1][j-2i]………………
f[i][j-i]=f[i-1][j-1]+f[i-1][j-2i]…………
可以转化为f[i][j]=f[i-1][j]+f[i][j-i];
优化为滚动数组
时间复杂度
参考文献
C++ 代码
#include<iostream>
//f[i][j]=f[i-1][j]+f[i][j-i];
using namespace std;
const int N=1010,mod=1e9+7;
int f[N];
int main(){
int n;
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];
}