状态压缩是一种常用于动态规划问题的技术，尤其适用于解决涉及多个状态的组合问题。它通过使用一个整数的位表示多个状态，从而大幅降低空间和时间复杂度。
状态压缩是用二进制进行压缩的,你需要了解位运算的基本运用:从集合论到位运算,当我们遇到处理数据很小的时候,比如n<20以内,可以考虑下状压。其中状压dp有相邻相关,相邻无关等类型，下面我会概述一下这两种类型的:

相邻无关：

https://leetcode.cn/problems/beautiful-arrangement/description/
通常只需要一个参数即可,因为只在乎有多少个数字参与,所以只需i = mask.bit_count() + 1即可统计目前有多少位参与计算

class Solution:
    def countArrangement(self, n: int) -> int:
        u = (1 << n) - 1
        @cache
        def dfs(mask):
            if mask==u:
                return 1
            res = 0
            i = mask.bit_count() + 1
            for j in range(n):
                if mask>>j&1==0 and ((j+1)%i==0 or i%(j+1)==0):
                    res += dfs(mask|1<<j)
            return res
        return dfs(0) 

等同于但尽量别使用下面的

class Solution:
    def countArrangement(self, n: int) -> int:
        @cache
        def dfs(i, mask):
            if i>n:
                return 1
            res = 0
            for j in range(n):
                if mask>>j&1==0 and ((j+1)%i==0 or i%(j+1)==0):
                    res += dfs(i+1, mask|1<<j)
            return res
        return dfs(1, 0) 

相邻相关:

这时候必须得至少2个参数,因为相邻相关,你得保存上一个数据
https://leetcode.cn/problems/special-permutations/submissions/

MOD = 10**9+7
class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        n =len(nums)
        u = (1 << n) - 1
        @cache
        def dfs(mask, i):
            if mask==u:
                return 1
            res = 0
            pre = nums[i]
            for j, y in enumerate(nums):
                if mask>>j&1==0 and (pre % y ==0 or y % pre ==0):
                    res = (dfs(mask|1<<j, j)+res)%MOD
            return res
        return sum(dfs(1<<i, i) for i in range(n))%MOD