DP For Counting

本文以一个问题介绍了计数型dp的一般做法

概念

计数 DP  是一种利用类似 DP 的记忆化搜索方法（与在狭义上的 DP，即最优化问题有一定区别），用于解决计数（以及求和）问题。

基本思想

计数问题一般指求一个集合 S 的大小，在 OI 中，S 的大小有时会达到 $O(N^N)$ 甚至 $O(2^{N!})$ 的级别(当然，一般会对某一个固定的数取模)，其中 N 是问题规模，所以我不能逐一求出 S 的元素。

如果我们能将 S 分成若十无交的子集，那么 S 的元素个数就等于这些分的元素个数的和。 果这些子集的计数恰好与原问题类似，那么我们就可以通过类似动态规划的方法来解决。

和最优化问题的区别

可以发现，计数 DP 和最优化 DP 都是在一入范围$\Omega$内求一个值（大小值、最优值），这入值通过将$\Omega$中的所有元素做一次处理，再对处理值做一次整合得到。

列如，对于 0-1 背包问题，$\Omega$中的元素为背包内的所有物品组成的集合，对于$\Omega$中的一入方案 S,对 S 做一次处理，处理得到的结果为w(s)为 S 中物品的总价值，对所有得到的处理值，我们取最大值，得到问题的答案。

对于计数问题，$\Omega$中的元素为要计算元素个数的集合 S，它的处理是把所有的 S 中元素变为 1，然后将这些 1 通过加法的方式汇总起来，因为每一个 S 中元素都对应一个 1，所以这样得到的值就是 S 中元素个数。

当汇总操作为最大/最小值时，我们可以将$\Omega$分成任意若于入部分，只需这些部分的并集为$\Omega$即可，无需无交的条件。而计数问题由于不满足这个条件，所以我们需要将$\Omega$分成若干个部分，这些部分两两无交，这就是与最优化 DP 的区别。

简单来说，计数问题要求将原问题中的目标集合划分为不重不漏的子集，一般来说子集代表了目标集合的一个元素，对这些子集求和来统计 S 的规模。而最优化问题的集合划分多半是有交集的，比较背包问题中一个规模更大的问题是规模较小问题的超集。

例题 整数划分

概述

一个正整数  n  可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中n1≥n2≥…≥nk ,k≥1。

我们将这样的一种表示称为正整数  n  的一种划分。

现在给定一个正整数  n，请你求出  n  共有多少种不同的划分方法。

试一试

状态表示

dp 数组为f[n][n] , f[i][j]表示为 将 j 划分为包含1 - i的降序序列的方案数。

递推

如何计算 f[i][j] , 我们考虑 可选的最大的数字i选择几个。这使得我们将j的可能排列划分为了不重不漏的状态，分别是 f[i-1][j-i] , f[i-1][j-i*2] ...... 。

图示可以看到，这也的划分方式保证序列是降序的。而f[i][j] 最终的结果就是这些子状态的答案之和。

边界

当刚好划分干净时。

也当然作为一种情况，所以任何一个 f[i][0] 都为 1。

f[0][j] 没有意义 ， 初始化f[1][j] 为 1 , 因为可选数字为 1 只有一种全 1 排列，从f[2][j] 开始递推。

注意

仔细品读f[i][j]的含义 ，不难理解f[i][j] , j < i的位置也有意义和对应的值。甚至可以看出 f[i][j] .st (j < i) = f[j][j]。

答案

答案存储在 f[n][n] 位置。

完整代码

#include<iostream>
using namespace std;

const int N = 1e3+10;
int f[N][N];

// f[i][j] 表示 从 1 - i 中 任选数字 组成数字 j 方案数
// 答案存储在 f[n][n] 位置

int main()
{
    int n; cin >> n;

    for(int i = 1 ; i <= n ; i++)
    {
        f[i][0] = f[1][i] = 1;
    }

    for(int j = 1 ; j <= n ; j++)
    {
        for(int i = 2 ; i <= n ; i++)
        {
            // 考虑 当i为最大的数字时 选择多少个 i
            // 如果刚好划分干净 那么 f[i-1][0]也要作为一种方案
            // 考虑 i 的边界 当 i == 1 便不能向前递推 f[1][j] 作为一种全1方案始终为1
            for(int k = 0 ; k * i <= j ; k++)
            {
                f[i][j] += f[i-1][j-k*i];
                f[i][j] %= int(1e9 + 7);
            }
        }
    }
    cout << f[n][n];
}