算法动态规划

计数DP：基于初等计数原理与容斥原理设计状态表示

字数统计: 2.6k字   |   阅读时长: 11分
, , ,

摘要: 带限制的排列数目

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个比较困难的计数问题。统计带有某种限制的排列数目，给定的参数有 $n, l, d$ 三个，其中 $n$ 是物品种类数，每种物品数量无限。$l$ 是排列的长度，$d$ 与限制条件有关。

状态表示与状态转移方程涉及到初等计数原理，不是很好想。此外还可以用容斥原理绕一下，这样还可以写出另一种状态表示。

本题也可以视为一个二元数列，通过生成函数求解数列通项，之后在生成函数的文章中会再回到本题。

$1 题目

你的音乐播放器里有 n 首不同的歌，在旅途中，你计划听 goal 首歌（不一定不同，即，允许歌曲重复）。你将会按如下规则创建播放列表：

  • 每首歌 至少播放一次 。
  • 一首歌只有在其他 l 首歌播放完之后才能再次播放。

给你 n、goal 和 l ，返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回对 109 + 7 取余 的结果。

示例 1：
输入：n = 3, goal = 3, l = 1
输出：6
解释：有 6 种可能的播放列表。[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1] 。

示例 2：
输入：n = 2, goal = 3, l = 0
输出：6
解释：有 6 种可能的播放列表。[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，[2, 2, 1]，[2, 1, 2]，[1, 2, 2] 。

示例 3：
输入：n = 2, goal = 3, l = 1
输出：2
解释：有 2 种可能的播放列表。[1, 2, 1]，[2, 1, 2] 。

提示：

1
0 <= l < n <= goal <= 100

$2 题解

算法1: 动态规划

给定 $n$ 首歌，给长度为 $l$ 的播放列表 $list$ 中填充歌曲，问有多少种填充方法。如果没有任何限制，这 $l$ 个位置每个位置都有 $n$ 种选择，总共 $n^{l}$ 种方法。

但这里有一个限制，就是相同的两首歌之间至少要相隔 $d$ 首歌。也就是当 $i + d + 1 > j$ 时，$list[i] \neq list[j]$。

分析与尝试

考虑在 $list$ 中一首一首填歌的过程，定义 $dp[i]$ 表示填前 $i$ 首歌的方案数，这里 $i$ 就是阶段要素。

附加信息比较难想，一个非常直接的方式是记最后一首歌为 $k$，这样定义 $dp[i][k]$ 表示前 $i$ 首歌，最后一首为 $k$ 的方案数。这样定义的话，答案就是 $\sum\limits_{1\leq k\leq n}dp[l][k]$。

但这样的附加信息粒度太细了，反而不好找到最优子结构。比如当第 $i$ 首歌为 $k$ 时，好像状态转移方程是下面这样：

虽然求和的时候把 $dp[i-1][k]$ 去掉了，但是 $j\neq k$ 时，$dp[i-1][j]$ 中还是含了 $list[i-2]$ 填 $k$ 的情况，而第 $i-d, i-d+1, \cdots, i-1$ 首歌都不能是 $k$，这样就构不成最优子结构，上述转移方程式错的。

最优子结构与状态表示

由于条件里有一个每首歌都至少放一次，最终填好的 $list$ 中就必须有 $l$ 首歌，对于最后一首歌 $list[n]$ 选 $k$ 的情况，分两种情况考虑：

  • 如果这就是 $list$ 中唯一的 $k$，那么前面 $l-1$ 个位置中就只有 $l-1$ 首歌了，这可以理解为给定的歌曲集合为 $l-1$ 个。
  • 如果前面还有其他位置填了 $k$，那么前 $l-1$ 个位置还是填了 $l$ 首歌。

上述两条合在一起，我们隐约发现了最优子结构，因此定义 $dp[i][k]$ 表示填前 $i$ 个位置，共填了 $k$ 首歌的方案数。这样答案就是 $dp[l][n]$。下面考虑状态转移方程。

状态转移方程

对于 $dp[i][k]$，考虑最后一首歌的两种情况，每种情况分别由初等计数原理给出对答案的贡献：

  • 如果最后一首歌 $a = list[i]$ 是 $list[1], \cdots, list[i]$ 中唯一一个 $a$，那么相当于 $list[0],\cdots,list[i-1]$ 填了 $k-1$ 首歌，方案数为 $dp[i-1][k-1]$。前 $i-1$ 个位置填了 $k-1$ 首，因此 $a$ 有剩下的 $n-k+1$ 种可选，所以这种情况对 $dp[i][k]$ 的贡献为 $(n-k+1)dp[i-1][k-1]$。
  • 如果最后一首歌 $a = list[i]$ 不是 $list$ 前 $i$ 个位置的唯一一个 $a$，则相当于 $list[0],\cdots,list[i-1]$ 还是填了 $k$ 首歌，方案数为 $dp[i-1][k]$。$a$ 可以在前 $i-1$ 个位置填充的 $k$ 首里选，但这里有个要求，就是第 $i-d,\cdots,i-1$ 这 $d$ 首是不能选的。因此 $a$ 有 $\max(k-d, 0)$。这种情况对 $dp[i][k]$ 的贡献为 $\max(k-d, 0)dp[i-1][k]$。

综上，状态转移方程为：

共 $O(nl)$ 个状态，状态转移需要 $O(1)$，总时间复杂度为 $O(nl)$。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numMusicPlaylists(int N, int L, int K) {
        int MOD = 1e9 + 7;
        using ll = long long;
        // dp[i][k] := 列表长 i, 含 k 首不同歌曲
        // i >= k
        vector<vector<int>> dp(L + 1, vector<int>(N + 1));
        dp[1][1] = 1;
        for(int i = 2; i <= L; ++i)
            for(int k = 1; k <= min(N, i); ++k)
            {
                dp[i][k] = ((ll)dp[i][k] + (ll)dp[i - 1][k] * max(j - K, 0)) % MOD;
                dp[i][k] = ((ll)dp[i][k] + (ll)dp[i - 1][k - 1] * (N - k + 1)) % MOD;
            }
        return dp[L][N];
    }
};

算法2: 容斥原理

给定 $n$ 首歌的集合，给长度为 $l$ 的播放列表 $list$ 中填充歌曲，相同的两首歌之间至少要相隔 $d$ 首歌。每首歌至少播放一次，问有多少种填法。

这里我们用容斥原理考虑答案的构成。记集合 $A$ 为不一定所有歌曲都至少播放一遍的方案集合；$B$ 表示一定有某些歌曲没有播放的方案。这样我们要求的实际上就是 $|A| - |B|$。关于容斥原理，下面是两篇参考文章：

状态表示

定义 $dp[k]$ 表示歌曲集合有 $k$ 首歌，填充长为 $l$ 的歌单，相同歌曲间隔至少 $d$，每首歌至少填充一次的方案数。

按照前面容斥原理的思路，$A[k]$ 表示不一定所有歌曲都至少播放一遍的方案数，$B[k]$ 表示一定有某些歌曲没有播放的方案数。这样 $dp[k] = A[k] - B[k]$。

状态转移方程

首先考虑 $A[k]$，可以用动态规划的方式解决。

考虑 $list$ 前 $i$ 个位置，可选歌曲有 $k$ 首，相同歌曲间隔至少 $d$，不一定所有歌曲都至少播放一遍的方案数，记其为 $f[i]$。这样初始值为 $f[1] = k$，下面考虑 $f[i]$ 的推导：

当 $1 < i \leq d + 1$ 时，第 $i$ 个位置除了前面填过的 $i - 1$ 首歌，剩下的 $k - i + 1$ 首歌可以随便选；当 $i > d + 1$，第 $i$ 个位置除了前面的 $d$ 首不能选，其余的 $k - d$ 首可以随便选，因此 $f$ 的转移方程如下：

$f[l]$ 就是当歌曲集合有 $k$ 个元素，填充长为 $l$ 的歌单，相同歌曲相隔至少 $d$，不一定所有歌曲都播放至少一遍的方案数。即 $A[k] = f[l]$。

下面考虑 $B[k]$，即可选歌曲有 $k$ 首，填充长为 $l$ 的列表，相同歌曲间隔至少 $d$，一定有某些歌曲没有播放的方案数。

初始值出现在当 $k\leq d$ 时，填充 $l$ 个清单位置时，两个相同歌曲之间无法间隔 $d$，因此 $B[k] = 0$。

当 $k > d$ 时，考虑出现在 $l$ 个位置中的歌曲，记其数目为 $j$，$d + 1 \leq j \leq k - 1$，那么有 $k - j$ 首歌没有出现，$1 \leq k - j \leq k - (d + 1)$。

从 $k$ 中选 $j$ 首歌的方法数有 $\binom{k}{j}$ 种，选出的 $j$ 首歌在 $l$ 个位置至少出现一次的方法数有 $dp[j]$。因此枚举所有可能的 $j$，即得 $B[k]$：

最终，状态转移方程为：

预处理组合数需要 $O(n^{2})$，$dp$ 需要推导 $O(n-d)$ 次，每次需要 $O(l)$ 计算一次 $A[k]$，以及 $O(n-d)$ 计算一次 $B[k]$。总时间复杂度为 $O(n^{2} + nl)$

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int numMusicPlaylists(int N, int L, int K) {
        // 预处理组合数组
        vector<vector<ll>> C(N + 1, vector<ll>(N + 1, 0)); 
        for(int k = 0; k <= N; ++k)
            C[k][0] = 1;
        for(int k = 1; k <= N; ++k)
            for(int j = 1; j <= min(k, N); ++j)
            {
                C[k][j] = C[k - 1][j] + C[k - 1][j - 1];
                C[k][j] %= MOD;
            }

        // dp[k] 表示歌曲集合有 k 个，填长为 l 的清单，相同歌曲间隔至少 d，每首歌至少出现一次的方案数
        vector<ll> dp(N + 1);
        for(int k = K + 1; k <= N; ++k) // 根据容斥原理计算每首都放的答案
        {
            int A = get_A(k, L, K);
            int B = 0;
            for(int j = K + 1; j < k; j++)
                B = ((B + C[k][j] * dp[j]) % MOD);   
            dp[k] = ((A - B) % MOD + MOD) % MOD;
        }

        return dp[N];
    }

    int get_A(int k, int l, int d)
    {
        // 计算不一定每首都放的答案
        vector<ll> f(l + 1);
        f[1] = k;
        for(int i = 2; i <= d + 1; i++)
        {
            f[i] = f[i - 1] * (k - i + 1);
            f[i] %= MOD;
        }
        for(int i = d + 2; i <= l; ++i)
        {
            f[i] = f[i - 1] * (k - d);
            f[i] %= MOD;
        }
        return f[l];
    }

private:
    const int MOD = 1e9 + 7;
    using ll = long long;
};
Share