526. 优美的排列

题目描述

给个一个数字n，表示有1-n的n个数，需要用这些数构造一个优美数组，数组下标从1开始
其中优美数组的定义：假设索引为i，i处的值是x，需要满足i%x0 或者 x%i0
问能构造的优美数组的数量？

基本分析

朴素做法：

1. 题目中给出的n很小，最大不超过15，暗示了哪些可能方法？回溯或者状态压缩dp
2. 如果考虑状态压缩dp，怎么定义数字的状态state？如果state的从右往左数第i为为1，表示i+1这个数被选取。举个例子n=6,\((011111)_2\)表示数字1，2，3，4，5都被选了
3. 下来考虑怎么定义dp的状态？定义f[i][state]表示考虑前列表的前i个数，且当前选择方案为state时的所有方案数量。需要注意的是（1）这里的i=0时表示不取任何数，i=1考虑前1个数，这个数可以取1-n中任何一个，而不是仅仅是i。（2）这里的state只是一个状态，为了获取到总数量，还要对第i位的数再进行一次枚举，这个在dp中用累加，在代码中进行了显式枚举
4. 枚举第i为的数字k的时候，需要考虑哪些条件？（1）当前的state第k-1位肯定需要是1，state>>(k-1)&11; (2)第i位能满足题目对数组的要求，k%i0 或者i%k==0
5. 考虑前i位，状态为state时怎么转移？枚举第i位的数字k，k需要满足以上2条要求，对每个可行的k，需要累加的值是f[i-1][state&(~(1<<(k-1)))]，这里的操作是什么意思？将state的第k位置0

以上朴素做法有啥缺陷？在决策第i位的时候，mask中1的个数应该也是i个，朴素的做法没有考虑这个关系，是n-2**n-n的枚举
考虑怎么优化以上做法？压缩第1个维度i

优化做法：

1. 怎么定义状态？状态state中包含了很多信息，直接从状态state出发，定义f[state]为当前选择数值为state时的所有方案数量
2. 考虑怎么计算f[state]?需要保证不重不漏。（1）state知道，那么选择的每个数字知道，位数也知道，枚举每个最后一位被选的数字；（2）从小到大遍历state，可以保证f[state]所依赖的状态都被计算到了
3. 怎么知道state中有多少个1？lowbit实现

代码

朴素做法

class Solution:
    def countArrangement(self, n: int) -> int:
        mask = 1<<n
        f = [[0]*mask for _ in range(n+1)]
        f[0][0] = 1
        for i in range(1, n+1):
            for state in range(0, mask):
                for k in range(1, n+1):
                    # 正常是第1位为1表示第1位占了，这里做了一个-1的偏移，k-1位为1表示k被选了
                    if  ((state >> (k-1)) & 1) == 0:
                        continue
                    if k % i !=0 and i % k != 0:
                        continue
                    f[i][state] += f[i-1][state & (~(1<<(k-1)))]

        return f[n][mask-1]

优化做法

class Solution:
    def getcnt(self, x):
        ans = 0
        while x:
            x -= (x&-x)
            ans +=1
        return ans

    def countArrangement(self, n: int) -> int:
        mask = 1 << n
        f = [0] * mask
        f[0] = 1

        for state in range(1, mask):
            # 计算state中1的个数，变相来求当前排序的长度
            cnt = self.getcnt(state)
            # 枚举最后一位数字，1对应i=0
            for i in range(n):
                if (state >>i & 1) == 0:
                    continue
                if (i+1) % cnt !=0 and cnt % (i+1) != 0:
                    continue
                f[state] += f[state & (~(1<<i))]
        
        return f[mask-1]

复杂度

时间：朴素为\(O(n^2*2^n)\), 优化为\(O(n*2^n)\)
空间：朴素为\(O(n*2^n), 优化为O(2^n)\)

总结