计数DP实例讲解

本篇主要从计数DP上结合实例分析。

一、计数类DP——整数划分

整数划分大体上可以分为3类

（1）考虑顺序的拆分方案（即1，1，2；和2，1，1 是两种不同的方案），这种问题一般转化为完全背包即可解决。

（2）不考虑顺序的拆分方案，可以划分出空集（也就是可以有对拆分完全没贡献的东西存在（0））

（3）不考虑顺序的拆分方案，要求划分出的集合不为空集（不可以拆出0）

主要讨论2，3类DP问题

二、空集存在的情况

对于n的m划分，可以定义dp[m][n]为所求答案， 考虑任意的拆分序列，可以分为两类

1. 所有都大于0，我们可以每个序列都拿出一个1，则拆分序列变为-1，它的求和为n−m，所以他是n − m的m划分 ,对答案的贡献为dp[i][j-i]。

2. 如果存在=0，可以将之化归到n的m − 1划分，对答案的贡献为dp[i-1][j]。

从而，有：

dp[i][j]=dp[i−1][j]+dp[i][j−1]

当划分的数量m太大(m>n)后,第一种情况不存在,

dp[i][j]=dp[i−1][j]

代码

#include <bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define debug(x) cout<<"> "<< x<<endl;
#define endl '\n'
#define lowbit(x) x&-x
//#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N =10 + 200, mod = 1e9 + 7;
int n,m;
ll dp[N][N];// j 的 i划分
void solve()
{    
    cin >> n >> m;
    // dp[i][j] = dp[i-1][j] + dp[i][j - i] 
    dp[0][0] = 1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=n;j++){
            if(j - i >= 0){
                dp[i][j] = dp[i][j-i] + dp[i-1][j];
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[m][n] << endl;
}
signed main()
{
    ios::sync_with_stdio();cin.tie();cout.tie();

    solve();

    return 0;
}

三、空集不存在的情况

在原来的基础上只要解决了重复计数的部分即可，显然就是不在考虑中存在0的情况，把上面代码else去掉。

并且注意初始化dp时,初始化为dp[m][0] = 1 ,防止重复计算

代码如下：

#include <bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define debug(x) cout<<"> "<< x<<endl;
#define endl '\n'
#define lowbit(x) x&-x
//#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N =10 + 200, mod = 1e9 + 7;
int n,m;
ll dp[N][N];// j 的 i划分
void solve()
{    
    cin >> n >> m;
    // dp[i][j] = dp[i-1][j] + dp[i][j - i] 
    dp[0][m] = 1;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(j - i >= 0){
                dp[i][j] = dp[i][j-i] + dp[i-1][j];
            }
        }
    }
    cout << dp[m][n] << endl;
}
signed main()
{
    ios::sync_with_stdio();cin.tie();cout.tie();

    solve();

    return 0;
}