526. 优美的排列

这是我参与8月更文挑战的第16天，活动详情查看：8月更文挑战

526. 优美的排列

假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：

第 i 位的数字能被 i 整除
i 能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？

示例1:

输入: 2
输出: 2
解释:

第 1 个优美的排列是 [1, 2]:
第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除

第 2 个优美的排列是 [2, 1]:
第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除
说明:

N 是一个正整数，并且不会超过15。

解题思路

数组含义

N 是一个正整数，并且不会超过15。所以我们可以使用int的低15位表示路径上是否排列上已经存在的整数，例如第5位为1，代表5已经加入排列了。因此我们可以使用一个int类型表示排列的状态，使用一个数组dp[i]存储排列情况为i时，构造的排列个数

状态转移

通过遍历1 <= j <= N，尝试将j插入当前i状态，如果j没有出现在排列中，并且满足整除关系，我们就将 当前构造出的排列个数，加入到新状态i|(1<<j)内

初始化

在0的状态下，排列个数为1

代码

class Solution {
    public int countArrangement(int n) {

       int[] dp=new int[1<<n];
      
       dp[0]=1; 
       for (int i=0;i<(1<<n);i++)
       {
           int wei=Integer.bitCount(i);
           for (int j=0;j<n;j++)
           {
               if((i&(1<<j))==0&&((j+1)%(wei+1)==0||(wei+1)%(j+1)==0))
                   dp[i|(1<<j)]+=dp[i];
           }
       }
       return dp[(1<<n)-1];


    }
}
复制代码