DAY20-动态规划(三)

今天要写的是状态压缩
DP在记录状态的时候有许多不同的方式，如果要记录的状态太多，或需要使用的维度太高，就会考虑使用状态压缩。
直接用例题来解释：

例题＆解释

访问所有节点的最短路径
题目叙述：给定一张无向图，返回任意选择一起点，访问完所有节点的最短路径长(可用相同的边)((也就是可以走回重复的点))
思路：
题目本身的问题并不复杂，就是选一个起点，从起点找完所有的节点，纪录最短的路径长，返回答案就好，思路本身也很简单，就是暴力法，把每一个种组合都找一次，问题只是实现，既然路径可以返回，就不能单纯只是记录每一个节点的访问或未被访问，这时候就需要状态压缩。
题目中，节点数量Ｎ小於12，所以可以用这种方式纪录：
vis{start}{mask}
start代表起始节点，mask代表访问的状态

MASK表示访问状态

要只用一个维度表示Ｎ个节点的访问状态，就是状态压缩的精髓，其实就是用位元来记录
ex. 00010可以代表从1号节点出发，还没访问过其他节点
00011可以代表1,2号节点都被访问过了

程序码实现

有了这种纪录方式之後，就对每一个起点ＢＦＳ就好，只要遇到有0111⋯⋯11这种状态（全部访问完成）就返回答案

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();

        queue< tuple<int, int, int> > q;
        vector<vector<bool>> vis(n, vector<bool>(1 << n));
        for(int i = 0; i < n; i++) {
            q.push({i, 1 << i, 0});
            vis[i][1 << i] = true;
        }
        while(!q.empty()) {
            auto [cur, mask, dist] = q.front();
            q.pop();

            if(mask == (1 << n) - 1) return dist;

            for(int x : graph[cur]) {
                int nextmask = mask | (1 << x);
                if(!vis[x][nextmask]) {
                    q.push({x, nextmask, dist + 1});
                    vis[x][nextmask] = true;
                }
            }
        }
        return 0;
        }
};