[动态规划](4)计数类DP
计数类DP
模板题:900. 整数划分 - AcWing题库
可将其看成一个 求 方案数 的完全背包问题 , 将 [ 1 ~ n ] 看作物品的体积, n 为背包容量 求所有能装满背包的方案数
思维导图:
代码:
```C++ //状态表示:f[i][j]表示只从1到i中选,且总和为j的方案数 //可将其看作一个完全背包模型,j表示当前背包容量
include
include
using namespace std; const int mod = 1e9+7; const int N = 1010; int f[N][N]; int n; int main(){ cin>>n;
f[0][0]=1;//表示从0当中选总和为0的有一种方案数
for(int i=1;i<=n;i++){//枚举从1到i中选,总和为j的方案数
for(int j=0;j<=n;j++){
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]<<endl;
return 0;
}