算法动态规划

状态压缩DP

字数统计: 1.4k字   |   阅读时长: 5分

摘要: 本文介绍状态压缩 DP 的原理和例题

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

本文参考《算法竞赛进阶指南》 0x5，书中关于状态压缩 DP 的讲解我觉得非常好。之前虽然解决过很多状态压缩 DP 的问题，例如 哈密顿路径，但是如何与动态规划中的阶段、状态、附加维度对应起来还不清楚。本文解决这个问题。

状态压缩 DP 的概念

在文章 动态规划概念和基础线性DP 中，我们了解到动态规划的过程是随着阶段的增长，在每个状态维度上不断扩展的。在任意时刻，已经求出最优解的状态与尚未求出最优解的状态在各维度上的分界点，组成了 DP 扩展的轮廓。

对于某些问题，我们需要在动态规划的状态中记录一个集合，保存这个轮廓的详细信息，以便于状态转移。

如果集合大小不超过 N，且集合中每个元素都是小于 K 的自然数，则我们可以把这个集合看做一个 N 位 K 进制数，以一个 $[0, K^{N} - 1]$ 之间的十进制整数的形式作为 DP 状态的一维(可以理解为 N 维状态压缩到 1 维)。这种把集合转化为整数记录在 DP 状态中的算法称为状态压缩 DP。

哈密顿路径问题的分析

关于哈密顿路径及其解法，可以看 哈密顿路径 这篇文章，这里从基本概念的角度分析一下。

对于哈密顿路径问题，我们在求解过程中，整个状态空间可以看做 N 维，每维度代表一个节点，每维度只有 0(未访问), 1(已访问) 两个值。DP 的轮廓以访问过的节点数目为阶段，从 (0, 0, …, 0) 扩展到 (1, 1, …, 1)。用一个 N 位二进制数表示各个节点的访问情况。另外需要知道最后经过的节点是哪个，将该节点编号作为附加状态。

算法如下

1
2
3
4
5
6
7
8
9
10
11
状态定义
dp[s][v] := 当前在 v 点，已经过的点集合为 s，从 0 到达 v 的最短路径

初始化
dp[1][0] = 0, (当前在 0 点，已经过的点集合只有 0)

答案
dp[(1 << n) - 1][n - 1]

状态转移
dp[s][v] = min(dp[s ^ (1 << v)][u] + a[u][v]) for u in s

题目: 棋盘覆盖

求把 N 行 M 列的棋盘分割成若干个 1 * 2 的的长方形，有多少种方案。

例如:

当 N=2，M=4 时，共有 5 种方案。

当 N=2，M=3 时，共有 3 种方案。

1 <= N,M <= 11

算法: 状态压缩 DP

对于任意一种方案，考虑以某一行为界，将棋盘分成上下两部分。

如图，考虑上半部分的最后一行

  1. 每个灰色背景的部分都是一个竖着的骨牌，决定了下一行必须继续补全该骨牌
  2. 其余部分对下一行的分割方法没有影响

因此，可以把行号作为 DP 的阶段，把上半部分不断向下扩展，直至确定整个棋盘。

为了描述最后一行的详细形态，用一个 M 位二进制数，其中第 k 位为 1 表示第 k 列是一个竖着的骨牌上半部分，为 0 表示其它情况。

第 i - 1 行形态为 s 的时候，想要在第 i 行形态为 t，需要满足以下 2 个条件。

  1. s 和 t 执行按位与的结果为 0 (每个 1 的下方必须是 0)
  2. s 和 t 执行按位或的结果的二进制表示中，每一段连续 0 都必须是偶数个(代表若干个横着的骨牌)

完整算法如下，其中 dp[0][s] 表示的是棋盘第一行上面假想的一行，与真正的第一行衔接，这样比较好写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
状态定义
dp[i][s] := 表示第 i 行的形态为 s 的时候，前 i 行的方案总数

答案
dp[N][0]

初始化
dp[0][0] = 1
dp[0][1..2^M-1] = 0

状态转移
dp[i][s] = sum(dp[i - 1][t])
    其中 s, t 满足条件
    (1) s & t = 0
    (2) s | t 的连续 1 长度均为偶数

代码 (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
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>

using namespace std;

bool check(const int x, const int M)
{
    // x 二进制的连续 0 长度均为偶数
    int i = M - 1;
    while(i >= 0)
    {
        int len = 0;
        while(i >= 0 && (x >> i & 1) == 0)
        {
            ++len;
            --i;
        }
        if(len & 1)
            return false;
        while(i >= 0 && (x >> i & 1) == 1)
            --i;
    }
    return true;
}

int main()
{
    using ll = long long;
    const int MAX_M = 11;
    int N = 11;
    vector<vector<vector<ll>>> dp_all(MAX_M + 1);
    for(int M = 1; M <= MAX_M; ++M)
    {
        vector<vector<ll>> dp(N + 1, vector<ll>(1 << M));
        dp[0][0] = 1;
        for(int i = 1; i <= N; ++i)
        {
            for(int s = 0; s < (1 << M); ++s)
            {
                for(int t = 0; t < (1 << M); ++t)
                {
                    if((s & t) != 0)
                        continue;
                    if(!check(s | t, M))
                        continue;
                    dp[i][s] += dp[i - 1][t];
                }
            }
        }
        dp_all[M] = dp;
    }
    int n, m;
    while(true)
    {
        cin >> n >> m;
        if(n == 0)
            break;
        cout << dp_all[m][n][0] << endl;
    }
}

LCP04-覆盖 的状态压缩 DP 的解法与本题很相似。

Share