【原创】状态压缩动态规划入门（状压dp）_状压dp入门

状态压缩动态规划简称状压dp，是一种通过二进制+dp的方法来解决问题的算法，一般来说这类算法适用于有n个任务，将n个任务全部完成需要的最小时间等（也可以用于棋盘问题等），此时我们需要构造$2^n$种状态来，考虑各个状态再得出答案。
状态压缩动态规划其实算是一种相对暴力的算法，其时间代价往往是指数级别的（速度还是比普通暴力法快很多），掌握状态压缩动态规划首先需要掌握位运算，这是状态压缩动态规划的基础。

位运算：
1.& ：参加运算的两个数据，按二进制位进行“与”运算。
运算规则： 0&0=0； 0&1=0； 1&0=0； 1&1=1

2.| ：参加运算的两个对象，按二进制位进行“或”运算。
运算规则： 0|0=0； 0|1=1； 1|0=1； 1|1=1

3.^ ：参加运算的两个数据，按二进制位进行“异或”运算。
运算规则： 0^0=0； 0^1=1； 1^0=1； 1^1=0

4.~ ：参加运算的一个数据，按二进制进行“取反”运算。
运算规则： ~1=0 ；~0=1

5.<< ：定义：将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。
设 a=1010 1110，a = a<< 2 将a的二进制位左移2位、右补0，即得a=1011 1000。（最高位不为1时，每左移一位相当于乘以2）

6 >> ：定义：将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。
例如：a=a>>2 将a的二进制位右移2位，左补0 或者 左补1得看被移数是正还是负。

算法步骤：
状态压缩动态规划算法基本可以分为三步：（以c++为例）
1.计算共有多少任务，建立数组；

vector<vector<int>> dp(n,vector<int>(1<<num_of_mission));
1

2.遍历所有情况，进行位运算来表达所有的情况；
3.建立动态规划方程。

例题
我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。

迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 ‘S’ 表示），和唯一的宝藏地点（用 ‘T’ 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 ‘M’ 表示），只有所有机关均被触发，才可以拿到宝藏。

要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 ‘O’ 表示），每个石堆都有无限个足够触发机关的重石。但是由于石头太重，我们一次只能搬一个石头到指定地点。

迷宫中同样有一些墙壁（用 ‘#’ 表示），我们不能走入墙壁。剩余的都是可随意通行的点（用 ‘.’ 表示）。石堆、机关、起点和终点（无论是否能拿到宝藏）也是可以通行的。

我们每步可以选择向上/向下/向左/向右移动一格，并且不能移出迷宫。搬起石头和放下石头不算步数。那么，从起点开始，我们最少需要多少步才能最后拿到宝藏呢？如果无法拿到宝藏，返回 -1 。

示例 1：
输入： [“S#O”, “M…”, “M.T”]

输出：16

解释：最优路线为： S->O, cost = 4, 去搬石头 O->第二行的M, cost = 3, M机关触发 第二行的M->O, cost = 3, 我们需要继续回去 O 搬石头。 O->第三行的M, cost = 4, 此时所有机关均触发 第三行的M->T, cost = 2，去T点拿宝藏。 总步数为16。

示例 2：

输入： [“S#O”, “M.#”, “M.T”]

输出：-1

解释：我们无法搬到石头触发机关

示例 3：

输入： [“S#O”, “M.T”, “M…”]

输出：17

解释：注意终点也是可以通行的。

限制：

1 <= maze.length <= 100
1 <= maze[i].length <= 100
maze[i].length == maze[j].length
S 和 T 有且只有一个
0 <= M的数量 <= 16
0 <= O的数量 <= 40，题目保证当迷宫中存在 M 时，一定存在至少一个 O 。

题解：
一个人在迷宫中，要从起点 SS 走到终点 TT。迷宫有两类特殊点，分别是：

MM：机关点，需要用石头触发
OO：石头点，一次可以搬一块石头
只有当所有 MM 点均被触发以后，终点才可到达，问起点走到终点的最小代价。

实际上，我们的走法只有四种：
1.从 S走到O
2.从O走到M
3.从M走到O
4.从M走到T

首先我们先要算出从S走到O再走到M所需的最短距离，在计算出从M走到最近的O再走到下一个M的最短距离，将其储存后再进行dp。（即先处理数据，得到最短路径）
我们使用nj（机关的数量）来建立状态压缩dp方程，我们定义$f(mask,i)$表示当前在第 i 个 M 处，触发状态为 mask 的最小步数，如果当前 mask 代表的已触发集合为 T，未触发集合为 U - T，则我们可以推出这样的动态规划转移方程：

其中 $maskxor{2}^i$ 表示把 $M_i$ 已触发的集合当中去掉，即 mask 这个状态可以由 $maskxor{2}^i$ 状态转移得到，转移时我们除了关注触发状态 mask 的变化，我们还关注是从哪一个 M 转移到了$M_i$，我们可以枚举 mask 当中已触发的所有的 $M_j(j\ne i)$ 作为上一个位置，而 d(j, i) 就是我们从 j 转移到 i 行走的最短步数，我们可以在预处理之后按照我们的策略得到所有的 d(j, i)（如果 i, j 不可达可以设为正无穷），然后 O(1) 查询，这就是预处理的目的。

class Solution {
public:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int n, m;

    bool inBound(int x, int y) {//边界判断
        return x >= 0 && x < n && y >= 0 && y < m;
    }

    vector<vector<int>> bfs(int x, int y, vector<string>& maze) {//从该点到所有位置的距离
        vector<vector<int>> ret(n, vector<int>(m, -1));
        ret[x][y] = 0;
        queue<pair<int, int>> Q;
        Q.push({x, y});
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            int x = p.first, y = p.second;
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (inBound(nx, ny) && maze[nx][ny] != '#' && ret[nx][ny] == -1) {
                    ret[nx][ny] = ret[x][y] + 1;
                    Q.push({nx, ny});
                }
            }
        }
        return ret;
    }

    int minimalSteps(vector<string>& maze) {
        int start_x,start_y,end_x,end_y;//开始位置和结束位置
        vector<pair<int,int>> stone,jiguan;//储存石头位置和机关位置
        n=maze.size();
        m=maze[0].size();

        for(int i=0;i<n;i++)//遍历数组，找各个位置
        {
            for(int j=0;j<m;j++)
            {
                if(maze[i][j]=='S')
                {
                    start_x=i;
                    start_y=j;
                }
                else if(maze[i][j]=='T')
                {
                    end_x=i;
                    end_y=j;
                }
                else if(maze[i][j]=='O')
                    stone.push_back({i, j});
                else if(maze[i][j]=='M')
                    jiguan.push_back({i, j});
            }
        }
        int ns=stone.size(),nj=jiguan.size();

        vector<vector<int>>start=bfs(start_x,start_y,maze);//建立初始点到各个点位置的二维数组
        if(nj==0)
            return start[end_x][end_y];
        
        vector<vector<int>>dict(nj,vector<int>(nj+2,-1));//表示两个机关之间的距离
        vector<vector<vector<int>>>dd(nj);
        for(int i=0;i<nj;i++)//储存最后一个M到终点的距离
        {
            vector<vector<int>> d=bfs(jiguan[i].first,jiguan[i].second,maze);
            dd[i]=d;
            dict[i][nj+1]=d[end_x][end_y];
        }
        for(int i=0;i<nj;i++)//S到O到M 的距离
        {
            int tmp=-1;
            for(int j=0;j<ns;j++)
            {
                int num1=stone[j].first,num2=stone[j].second;
                if(dd[i][num1][num2]!=-1 && start[num1][num2]!=-1){
                    if (tmp == -1 || tmp > dd[i][num1][num2] + start[num1][num2]) 
                        tmp = dd[i][num1][num2] + start[num1][num2];
                }

            }
            dict[i][nj]=tmp;
            for(int j=i+1;j<nj;j++)//M到O到M'的距离
            {
                int temp=-1;
                for(int k=0;k<ns;k++)
                {
                    int num1=stone[k].first,num2=stone[k].second;
                    if(dd[i][num1][num2]!=-1 && dd[j][num1][num2]!=-1)
                    {
                        if(temp==-1 || temp>dd[i][num1][num2]+dd[j][num1][num2])
                            temp=dd[i][num1][num2]+dd[j][num1][num2];
                    }
                }
                dict[i][j]=temp;
                dict[j][i]=temp;
            }
        }
        for (int i = 0; i < nj; i++)//边界条件
            if (dict[i][nj] == -1 || dict[i][nj + 1] == -1) return -1;

        vector<vector<int>>dp(1<<nj,vector<int>(nj+1,-1));//建立动态规划方程
        for (int i = 0; i < nj; i++) {
            dp[1 << i][i] = dict[i][nj];
        }
        for(int mask=1;mask< (1<<nj);mask++)
        {
            for(int i=0;i<nj;i++)
            {
                if(mask & (1<<i))
                {
                    for(int j=0;j<nj;j++)
                    {
                        if(!(mask & (1<<j)))
                        {
                            int next = mask | (1 << j);
                            if (dp[next][j] == -1 || dp[next][j] > dp[mask][i] + dict[i][j]) 
                                dp[next][j] = dp[mask][i] + dict[i][j];
                        }
                    }
                }
            }
        }
        int ret = -1;
        int final_mask = (1 << nj) - 1;
        for (int i = 0; i < nj; i++) {//最后一个M到T的距离
            if (ret == -1 || ret > dp[final_mask][i] + dict[i][nj + 1]) {
                ret = dp[final_mask][i] + dict[i][nj + 1];
            }
        }
        return ret;
    }
};
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134