1.题目基本信息

1.1.题目描述

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

• perm[i] 能够被 i 整除

• i 能够被 perm[i] 整除

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

1.2.题目地址

https://leetcode.cn/problems/beautiful-arrangement/description/

2.解题方法

2.1.解题思路

记忆化搜索+状态压缩 / 动态规划

2.2.解题步骤

思路1：记忆化搜索+状态压缩

• 第一步，定义深搜函数。dfs(s)中s表示当前还没有使用的数字的二进制状态，返回能够构建的「优美排列」的个数

• 第二步，递归出口，dfs(0)=1，表示所有的数字已经填写完，构成一种合法的情况

• 第三步，递推公式。dfs(s)=sum(dfs(s&~(1<<(j-1))) for j in range(1,n+1) if j在状态s中 and (j是i的倍数或者i是j的倍数))（i为当前数组填写的位置索引，等于s中1的个数）

• 第四步，dfs((1<<n)-1)即为题解

思路2：记忆化搜索1:1转动态规划

• 第一步，状态定义。dp[s]表示在未使用的数字的二进制状态为s时，用这些数字能够构建成的「优美排列」的个数

• 第二步，状态初始化。df[0]=1

• 第三步，状态转移。dp[s]=sum(dp[s&~(1<<(j-1))] for j in range(1,n+1) if j在状态s中 and (i是j的倍数或者j是i的倍数))（i为当前数字填写的位置，等价于s二进制中1的个数）

• 第四步，最终的dp[(1<<n)-1]即为题解

3.解题代码

python3代码-记忆化搜索+状态压缩

class Solution:
    def countArrangement(self, n: int) -> int:
        # 思路1：记忆化搜索+状态压缩
        # 第一步，定义深搜函数。dfs(s)中s表示当前还没有使用的数字的二进制状态，返回能够构建的「优美排列」的个数
        @cache
        def dfs(s:int) -> int:
            ans = 0
            # 第二步，递归出口，dfs(0)=1，表示所有的数字已经填写完，构成一种合法的情况
            # > i表示当前数组中填的位置索引
            i = s.bit_count()
            if i == 0:
                return 1
            # 第三步，递推公式。dfs(s)=sum(dfs(s&~(1<<(j-1))) for j in range(1,n+1) if j在状态s中 and (j是i的倍数或者i是j的倍数))（i为当前数组填写的位置索引，等于s中1的个数）
            # j表示当前的候选填的数字
            for j in range(1, n + 1):
                if (s >> (j - 1) & 1) and (j % i == 0 or i % j == 0):
                    ans += dfs(s & ~(1 << (j - 1)))
            return ans
        # 第四步，dfs((1<<n)-1)即为题解
        return dfs((1 << n) - 1)

python3代码-动态规划

class Solution:
    def countArrangement(self, n: int) -> int:
        # 思路2：记忆化搜索1:1转动态规划
        # 第一步，状态定义。dp[s]表示在未使用的数字的二进制状态为s时，用这些数字能够构建成的「优美排列」的个数
        dp = [0] * (1 << n)
        # 第二步，状态初始化。df[0]=1
        dp[0] = 1
        # 第三步，状态转移。dp[s]=sum(dp[s&~(1<<(j-1))] for j in range(1,n+1) if j在状态s中 and (i是j的倍数或者j是i的倍数))（i为当前数字填写的位置，等价于s二进制中1的个数）
        for s in range(1, 1 << n):
            i = s.bit_count()
            for j in range(1, n + 1):
                if (s >> (j - 1)) & 1 and (i % j == 0 or j % i == 0):
                    dp[s] += dp[s & ~(1 << (j - 1))]
        # 第四步，最终的dp[(1<<n)-1]即为题解
        return dp[(1 << n) - 1]

4.执行结果