Leetcode 2741. Special Permutations

[Woodyiiiiiii]

2741. Special Permutations

2741. Special Permutations
状压 DP
1187. Make Array Strictly Increasing

这道题目，如果一开始就从暴力开始考虑，那这就是个全排列问题，也就是队列中顺序问题。我一开始看到数组大小，以为这样暴力的时间复杂度是O(2^n)，所以不会TLE，结果还是超时了。

那其实这是另外一个关键点，全排列问题不同于子集问题，时间复杂度是O(n!)，所以耗时非常大。

那接下来就是优化了，看到数组大小，很容易想到状压DP，利用状态压缩优化状态，减少不必要的时间消耗。

那我们不妨从记忆化搜索开始考虑，接下来是如何设置缓存呢？难点在这里。那不如从已知条件上出发，那就是关键的状态表示位mask和位置i。首先考虑到所有状态，用位表示就有2^14，完全够用。那这么点状态能做缓存吗？这就要关联上一个状态了(全排列特点)。假设dfs(mask,j)表示上一个位置是j时的所有能取mask的结果个数，这样就能表示所有状态。

状态压缩的精髓在于，124和214是一样的，因为已经遍历过了，所以状态被压缩到mask，也就是2^n而不是n!了。

class Solution {
    final int MOD = (int) (1e9 + 7);
    int[] nums;
    int n;
    long[][] dp;

    public int specialPerm(int[] nums) {
        n = nums.length;
        this.nums = nums;
        dp = new long[n][1 << n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1L);
        }
        int t = (1 << n) - 1;
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += dfs(i, t ^ (1 << i));
            // System.out.println(ans);
            ans %= MOD;
        }
        return (int)ans;
    }

    private long dfs(int i, int mask) {
        if (mask == 0) {
            return 1;
        }
        if (dp[i][mask] != -1) {
            return dp[i][mask];
        }

        long res = 0;
        for (int j = 0; j < n; j++) {
            if ((mask & (1 << j)) == (1 << j) &&
                    (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                res += dfs(j, mask ^ (1 << j));
                res %= MOD;
            }
        }

        dp[i][mask] = res;
        return res;
    }

}

时间复杂度的计算是状态 * 单个状态计算时间。总共有n * 2^n个状态，每个状态获取时间是n，所以时间复杂度是O(n^2 * 2^n)。

我在比赛中受到了No.1187的启发，用哈希表来表示缓存，有用copilot的嫌疑...

class Solution {
    final int MOD = (int) (1e9 + 7);
    int[] nums;
    int n;
    Map<Integer, Set<Integer>> factorMap2;
    Map<Integer, Long>[] memo;

    public int specialPerm(int[] nums) {
        n = nums.length;
        this.nums = nums;
        factorMap2 = new HashMap<>();

        memo = new HashMap[1 << n];
        for (int i = 0; i < (1 << n); i++) {
            memo[i] = new HashMap<>();
        }

        for (int i = 0; i < n; i++) {
            // 获得当前数字的所有因数
            List<Integer> factors = getFactors(nums[i]);
            factorMap2.putIfAbsent(nums[i], new HashSet<>());
            factorMap2.get(nums[i]).addAll(factors);
        }
        return (int) dfs(0, 0, -1);
    }

    private long dfs(int i, int mask, int pre) {
        if (i == n) {
            return 1;
        }
        if (memo[mask].containsKey(pre)) {
            return memo[mask].get(pre);
        }

        long res = 0;
        for (int j = 0; j < n; j++) {
            if ((mask & (1 << j)) == 0 &&
                    ((pre == -1 ||
                            (factorMap2.get(pre).contains(nums[j]) || factorMap2.get(nums[j]).contains(pre)) || pre == 1 || nums[j] == 1))) {
                res += dfs(i + 1, mask | (1 << j), nums[j]);
                res %= MOD;
            }
        }
        memo[mask].put(pre, res);
        return res;
    }

    private List<Integer> getFactors(int num) {
        List<Integer> factors = new ArrayList<>();
        // 排除1
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                factors.add(i);
                if (i * i != num) {
                    factors.add(num / i);
                }
            }
        }
        if (num != 1) {
            factors.add(num);
        }
        return factors;
    }
}

试试由递翻译成归。