[动态规划](4)计数类DP

计数类DP

模板题:900. 整数划分 - AcWing题库

可将其看成一个 求 方案数 的完全背包问题 ， 将 [ 1 ~ n ] 看作物品的体积， n 为背包容量 求所有能装满背包的方案数

思维导图：

代码:

//状态表示:f[i][j]表示只从1到i中选,且总和为j的方案数
//可将其看作一个完全背包模型，j表示当前背包容量
#include<iostream>
#include<algorithm>
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;
}

本文链接：