状压DP

526. 优美的排列

class Solution {
public:
    int countArrangement(int n) {
        int mask = 1 << n;
        vector<vector<int>> f(n + 1, vector<int>(mask, 0));

        f[0][0] = 1; // 考虑前i个数，状态为0的方案数（优美排列数量）
        for (int i = 1; i <= n; i ++)   // 枚举当前位置
            for (int state = 1; state <= mask; state ++)  // 枚举当前状态，0为选该数，1为不选
                for (int k = 1; k <= n; k ++)  {  // 枚举当前位置填了什么数
                    if (!((state >> (k - 1)) & 1)) continue;  // 如果当前数在状态中为0，则跳过
                    if (k % i && i % k) continue; // 不满足任何整除关系
                    // state & (~(1 << (k - 1))) 代表将 state 中数值 k 的位置置零
                    f[i][state] += f[i - 1][state & ~(1 << (k - 1))];
                }
        return f[n][mask - 1];
    }
};

847. 访问所有节点的最短路径

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int mask = 1 << n;
        vector<vector<int>> dist(mask, vector<int>(n + 1, INT_MAX)); // state和u(该状态下的最后一步)对应的步数
        deque<vector<int>> d; // 存储state 和 u
        for (int i = 0; i < n; i ++) {
            dist[1 << i][i] = 0;
            d.push_back({1 << i, i});
        }
        while (!d.empty()) {
            auto poll = d.front();
            d.pop_front();
            int state = poll[0], u = poll[1], step = dist[state][u];
            if (state == mask - 1) return step;
            for (int i: graph[u]) {
                if (dist[state | (1 << i)][i] == INT_MAX) {
                    dist[state | (1 << i)][i] = step + 1;
                    d.push_back({state | (1 << i), i});
                }
            }
        }
        return -1;
    }
};