法1: 回溯

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def countArrangement(self, n: int) -> int:
        self.num = 0
        mat = defaultdict(list)
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if i % j == 0 or j % i == 0:
                    mat[i].append(j)

        def recur(k):
            if k == n + 1:
                self.num += 1
                return
            
            for i in mat[k]:
                if i not in v:
                    v.add(i)
                    recur(k + 1)
                    v.remove(i)
        
        v = set()
        recur(1)
        return self.num

法2: DP状态压缩，参考题解：宫水三叶

使用二进制序列state表示选择的数字（若选择k则将第k位置为1）。枚举所有二进制状态state，设法计算其中1的数量也就是当前选择序列的长度，然后枚举当前最后一位i的数值。要求满足state中第i位为1且符合题目对于整除的两个要求之一。此状态下的排列数量等于此状态原有排列数量加上state中当前位置i置为0的“上一状态”的优美排列数量。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import Counter

class Solution:
    def countArrangement(self, n: int) -> int:
        mask = 1 << n
        f = [0 for _ in range(mask)]
        f[0] = 1
        for state in range(mask):
            cnt = Counter(str(bin(state)))['1']
            for i in range(1, n + 1):
                if (state & (1 << (i-1))) == 0: continue
                if cnt == 0: continue
                if i % cnt != 0 and cnt % i != 0: continue
                f[state] += f[state & (~(1 << (i-1)))]
        return f[mask-1]