0526：优美的排列（★）

力扣第 526 题

题目

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：

• perm[i] 能够被 i 整除
• i 能够被 perm[i] 整除

给你一个整数 n ，返回可以构造的 优美排列 的 数量 。

示例 1：

输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
- perm[1] = 1 能被 i = 1 整除
- perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
- perm[1] = 2 能被 i = 1 整除
- i = 2 能被 perm[2] = 1 整除

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 15

分析

假设最后一个数是 x，满足 x%n==0 或 n%x==0， 那么剩下的转为子问题：求集合 set(range(1,n+1))-{x} 中构造优美排列的个数。

所以令 dfs(A) 代表集合 A 构造的优美排列个数，即可递归。

为了方便，可以将集合状态压缩为一个数。

解答

1
2
3
4
5
6
7
8

def countArrangement(self, n: int) -> int:
    dp = [1]+[0]*((1<<n)-1)
    for st in range(1<<n):
        idx = bin(st).count('1')+1
        for x in range(n):
            if not st&(1<<x) and ((x+1)%idx==0 or idx%(x+1)==0):
                dp[st|(1<<x)] += dp[st]
    return dp[-1]

160 ms