计数类dp
整数划分
法1(自己想的,比较慢)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10,mod=1e9+7;
int f[N][N];
ll ans;
int main(){
int n;
cin>>n;
//初始化
for(int i=1;i<=n;i++){
f[i][i]=1;
}
//dp
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
for(int k=1;k<=min(i-j,j);k++){
f[i][j]+=f[i-j][k];
f[i][j]%=mod;
}
}
}
for(int i=1;i<=n;i++){
ans+=f[n][i];
ans%=mod;
}
cout<<ans;
return 0;
}
法2(转为类似完全背包的形式)
/*
f[i,j]这个集合表示,从1~i这几个数中选,总和(总体积)恰为j的数
可以优化成f[j]
*/
#include<bits/stdc++.h>
using namespace std;
int f[1010];
const int mod=1e9+7;
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-i];
f[j]%=mod;
}
}
cout<<f[n];
return 0;
}
法3
/*
f[i,j]这个集合表示:总和为i,恰为j个数的和的方案
这里的难点在于如何保证不重不漏
所以这里的划分方式会比较难想:
用最小值为1或大于1来划分(具体看图)
*/
#include<bits/stdc++.h>
using namespace std;
int f[1010][1010];
const int mod=1e9+7;
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-1][j-1]+f[i-j][j];
f[i][j]%=mod;
//一个保证最小值为1,就填个1
//另一个最小值大于1,就全加1
}
}
long long ans=0;
for(int i=1;i<=n;i++){
ans+=f[n][i];
ans%=mod;
}
cout<<ans;
return 0;
}