https://www.acwing.com/problem/content/902/

整数划分问题，给定一个正整数n，问有多少种方案使得n=x1+x2+...+xn，不考虑顺序。

解法1：利用完全背包的模型，将1~n每一个数字看成一个物品。

 

 

 1 #include<iostream>
 2 using namespace std;
 3 const int N=1010,mod=1e9+7;
 4 int f[N][N];
 5 int main(void){
 6     int n;
 7     cin>>n;
 8     for(int i=0;i<=n;i++) f[i][0]=1;//初始化，表示在前i个中选，和为0的方案数都为1
 9     for(int i=1;i<=n;i++){
10         for(int j=1;j<=n;j++){
11             f[i][j]=f[i-1][j];
12             if(j>=i) f[i][j]+=f[i][j-i];
13             f[i][j]%=mod;
14         }
15     }
16     cout<<f[n][n];
17     return 0;
18 }

 

空间优化

 1 #include<iostream>
 2 using namespace std;
 3 const int N=1010,mod=1e9+7;
 4 int f[N];
 5 int main(void){
 6     int n;
 7     cin>>n;
 8     f[0]=1;
 9     for(int i=1;i<=n;i++){
10         for(int j=i;j<=n;j++){
11             f[j]=(f[j]+f[j-i])%mod;
12         }
13     }
14     cout<<f[n];
15     return 0;
16 }

 

解法2:

 

 

 1 #include<iostream>
 2 using namespace std;
 3 const int N=1010,mod=1e9+7;
 4 int f[N][N];
 5 int main(void){
 6     int n;
 7     cin>>n;
 8     f[1][1]=1;//表示总和为1，个数为1的方案数为1.
 9     for(int i=2;i<=n;i++){
10         for(int j=1;j<=i;j++){
11             f[i][j]=(f[i-1][j-1]+f[i-j][j])%mod;
12         }
13     }
14     int res=0;
15     for(int i=1;i<=n;i++) res=(res+f[n][i])%mod;
16     cout<<res;
17     return 0;
18 }