编程笔记

计数类DP

3分钟阅读

4.计数类DP

AcWing 900. 整数划分

实现思路：本题求的是方案个数，而不要求方案顺序，即4=1+1+2 和4=1+2+1是一样的

（1）方案一：转化为完全背包做法。将正整数n看做是背包容量，而1~n之间的数看做是物品，且各个物品的数量是无限的，至此转化为完全背包问题。

  • f(i,j)表示从前i个数字（物品）中选择，之和恰好是j（体积）的方案个数

  • 以第i个数字选择了几次（物品i放了几个）做集合划分。若只选0个i，那么前i-1数的选择之和已经满足j，故为f[i-1][j]；若第i个数字选择了k次，那么前i-1个数的选择之和为j-k*v[i]，故f[i-1][j-v[i]]

  • 类似完全背包问题的分析与优化：

    f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2i] + .... + f[i - 1][j - k*i]

    f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2i] + .... + f[i - 1][j - k*i]

  • 所以：

    状态转移方程：f[i][j] = f[i - 1][j] + f[i][j - i]

    优化至一维

    f[j] = f[j] + f[j - i]表示和为j的方案数量

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010,mod=1e9+7;//最后结果要取模
int n,f[N];
int main(){
    cin>>n;
    f[0]=1;//和为0，那就一种选法
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)//j正序，且从i开始 省去判断j-i是否大于0
            f[j]=(f[j]+f[j-i])%mod;
    
    cout<<f[n]<<endl;
    return 0;
}

（2）方案二：

  • 用f[i][j]表示，所有总和是i，并且恰好表示成j个数之和的方案的数量。

  • 集合划分，能够分为如下两类

    • 方案中最小值是1的所有方案，这时候去掉一个1，此时和变成了i - 1 ，个数变成了j - 1 ，即f[i - 1][j - 1]
    • 方案中最小值大于1的所有方案，此时将j个数都减去1，此时和变成了i - j(j个数每个数都-1，共-j)，个数还是j，即f[i - j][j]

  • 最终状态转移方程为：f[i][j] = f[i - 1][j-1] + f[i-j][j]

  • 结果输出应为f[n][1] + f[n][2] + f[n][3] + … + f[n][n]

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010,mod=1e9+7;
int n,f[N][N];
 
int main(){
    cin>>n;
    f[0][0]=1;//和为0 0个数表示的方案为1
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)//和为i 最多表示为i个数的和(即i个1的和)
            f[i][j]=(f[i-1][j-1]+f[i-j][j])%mod;
    int res=0;
    for(int i=0;i<=n;i++)
        res+=f[n][i];
    cout<<res<<endl;
    
    return 0;
}