计数类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;

}

本文链接：