How can I solve the Special Permutations problem efficiently?

Use dynamic programming with bitmasking to track subsets of the array and apply the divisibility condition during state transitions.

What is the main approach to solving Special Permutations?

The main approach is dynamic programming with bitmasking, where each bit represents an element in the array and the states transition based on divisibility conditions.

What are common mistakes in solving Special Permutations?

Common mistakes include forgetting the modulo operation, mishandling state transitions, and inefficient bitmasking.

How does GhostInterview help in solving the Special Permutations problem?

GhostInterview helps by providing efficient dynamic programming strategies and clarifying the use of bitmasking and modulo operations.

Can this problem be solved without dynamic programming?

While dynamic programming with bitmasking is the most efficient approach, solving the problem without it would likely be computationally expensive and inefficient.

#2741

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

特别的排列

给你一个下标从 0 开始的整数数组 nums ，它包含 n 个互不相同的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：对于 0 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。请你返…

数组动态规划位运算位掩码

题目描述

给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：

对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。

请你返回特别排列的总数目，由于答案可能很大，请将它对 10⁹+ 7 取余后返回。

示例 1：

输入：nums = [2,3,6]
输出：2
解释：[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。

示例 2：

输入：nums = [1,4,3]
输出：2
解释：[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。

提示：

2 <= nums.length <= 14
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：状态压缩动态规划

我们注意到题目中数组的长度最大不超过 $14$ ，因此，我们可以用一个二进制整数来表示当前的状态，其中第 $i$ 位为 $1$ 表示数组中的第 $i$ 个数已经被选取，为 $0$ 表示数组中的第 $i$ 个数还未被选取。

我们定义 $f[i][j]$ 表示当前选取的整数状态为 $i$ ，且最后一个选取的整数下标为 $j$ 的方案数。初始时 $f[0][0]=0$ ，答案为 $\sum_{j=0}^{n-1}f[2^n-1][j]$ 。

考虑 $f[i][j]$ ，如果当前只有一个数被选取，那么 $f[i][j]=1$ 。否则，我们可以枚举上一个选择的数的下标 $k$ ，如果 $k$ 与 $j$ 对应的数满足题目要求，那么 $f[i][j]$ 可以从 $f[i \oplus 2^j][k]$ 转移而来。即：

f[i][j]= \begin{cases} 1, & i=2^j\\ \sum_{k=0}^{n-1}f[i \oplus 2^j][k], & i \neq 2^j \textit{且} \textit{nums}[j] \textit{与} \textit{nums}[k] \textit{满足题目要求}\\ \end{cases}

最终答案即为 $\sum_{j=0}^{n-1}f[2^n-1][j]$ 。注意答案可能很大，需要对 $10^9+7$ 取模。

时间复杂度 $O(n^2 \times 2^n)$ ，空间复杂度 $O(n \times 2^n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        m = 1 << n
        f = [[0] * n for _ in range(m)]
        for i in range(1, m):
            for j, x in enumerate(nums):
                if i >> j & 1:
                    ii = i ^ (1 << j)
                    if ii == 0:
                        f[i][j] = 1
                        continue
                    for k, y in enumerate(nums):
                        if x % y == 0 or y % x == 0:
                            f[i][j] = (f[i][j] + f[ii][k]) % mod
        return sum(f[-1]) % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates a clear understanding of dynamic programming with bitmasking.
question_mark
The candidate successfully applies state transition methods to the problem.
question_mark
The candidate efficiently manages large numbers using modulo operations.

warning

常见陷阱

外企场景

error
Forgetting to apply the modulo operation at each step, leading to overflow.
error
Incorrectly handling the state transitions, such as failing to check the divisibility condition between consecutive elements.
error
Not efficiently managing bitmasking, resulting in redundant calculations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Considering additional constraints such as larger arrays or different divisibility conditions.
arrow_right_alt
Applying different dynamic programming strategies for state transitions.
arrow_right_alt
Optimizing the solution for faster execution with larger inputs.

help

常见问题

外企场景

继续练习

#2572 无平方子集计数 #3149 找出分数最低的排列 #2305 公平分发饼干