题目描述
一个正整数 n 可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n,请你求出 n 共有多少种不同的划分方法。
输入格式
共一行,包含一个整数 n。
输出格式
共一行,包含一个整数,表示总划分数量。
由于答案可能很大,输出结果请对 109+7 取模。
数据范围
1≤n≤1000
输入样例:
5
完全背包解法
朴素版三种写法
1三重循环
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int n,f[N][N];
int main(){
cin>>n;
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++){
for(int k=0;k*i<=j;k++){
f[i][j]+=f[i-1][j-k*i];
f[i][j]%=mod;
}
}
cout<<f[n][n];
return 0;
}
2初始化f[0][0],并优化为二重循环
优化时等价:f[i-1][j-k*i]==f[i][j-i]
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int n,f[N][N];
int main(){
cin>>n;
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)//这里下标j从0开,
{
f[i][j]=f[i-1][j]%mod;
if(j>=i) f[i][j]=(f[i-1][j]+f[i][j-i])%mod;
}
cout<<f[n][n];
return 0;
}
3初始化f[1~n][0],并优化为二重循环
按照逻辑不选i组成0,为1种方案。故f[1~n][0]均为1,但是下面二重循环j要从1开始了
前面两种f[0][0]=1,二重循环j从0开始,都是f[1][0]开始用到f[0][0]的值
这里想说按照想法来看,集合是从1~n中选,0不能选,f[0][0]没有初始值,下面j从1开始
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int n,f[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) f[i][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)//这里下标j从1开始
{
f[i][j]=f[i-1][j]%mod;
if(j>=i) f[i][j]=(f[i-1][j]+f[i][j-i])%mod;
}
cout<<f[n][n];
return 0;
}
一维数组优化版
和完全背包一样
#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int n,f[N];
int main(){
cin>>n;
f[0]=1;//1~n不选都为1种方案
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
f[j]=(f[j]+f[j-i])%mod;//用到的是这一层的j-i
cout<<f[n];
return 0;
}