Medium

题目描述

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

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

返回特殊排列的总数。由于答案可能很大，返回它对 10^9 + 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^9

解题思路

这是一个典型的状态压缩动态规划问题。由于数组长度不超过14，我们可以用位掩码来表示已使用的元素集合。

核心思路：

  1. 状态定义：dp[mask][last] 表示已使用元素集合为 mask，且排列最后一个元素下标为 last 的特殊排列数量
  2. 状态转移：对于当前状态 dp[mask][last]，枚举所有未使用的元素 i，如果 nums[last] 和 nums[i] 满足整除关系，则可以转移到状态 dp[mask|(1<<i)][i]
  3. 边界条件：单个元素的排列数为1，即 dp[1<<i][i] = 1
  4. 最终答案：所有长度为n的排列数之和

优化细节：

  • 预处理所有元素对之间的整除关系，避免重复计算
  • 使用记忆化搜索或者自底向上的DP都可以
  • 注意取模运算

由于n最大为14，状态数量为 2^14 * 14 ≈ 230,000，完全可以接受。

推荐解法：状态压缩DP + 记忆化搜索，代码简洁且易理解。

代码实现

class Solution {
public:
    int specialPerm(vector<int>& nums) {
        int n = nums.size();
        const int MOD = 1e9 + 7;
        
        // 预处理整除关系
        vector<vector<bool>> canConnect(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                    canConnect[i][j] = true;
                }
            }
        }
        
        // dp[mask][last] = 以last结尾，使用了mask集合的排列数
        vector<vector<long long>> dp(1 << n, vector<long long>(n, -1));
        
        function<long long(int, int)> dfs = [&](int mask, int last) -> long long {
            if (__builtin_popcount(mask) == 1) {
                return 1;
            }
            
            if (dp[mask][last] != -1) {
                return dp[mask][last];
            }
            
            long long res = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) && i != last && canConnect[i][last]) {
                    res = (res + dfs(mask ^ (1 << last), i)) % MOD;
                }
            }
            
            return dp[mask][last] = res;
        };
        
        long long ans = 0;
        int fullMask = (1 << n) - 1;
        for (int i = 0; i < n; i++) {
            ans = (ans + dfs(fullMask, i)) % MOD;
        }
        
        return ans;
    }
};

class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        n = len(nums)
        MOD = 10**9 + 7
        
        # 预处理整除关系
        can_connect = [[False] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if i != j and (nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0):
                    can_connect[i][j] = True
        
        # 记忆化搜索
        @cache
        def dfs(mask, last):
            if bin(mask).count('1') == 1:
                return 1
            
            res = 0
            for i in range(n):
                if (mask & (1 << i)) and i != last and can_connect[i][last]:
                    res = (res + dfs(mask ^ (1 << last), i)) % MOD
            
            return res
        
        ans = 0
        full_mask = (1 << n) - 1
        for i in range(n):
            ans = (ans + dfs(full_mask, i)) % MOD
        
        return ans

public class Solution {
    public int SpecialPerm(int[] nums) {
        int n = nums.Length;
        const int MOD = 1000000007;
        
        // 预处理整除关系
        bool[,] canConnect = new bool[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                    canConnect[i, j] = true;
                }
            }
        }
        
        // dp[mask][last] = 以last结尾，使用了mask集合的排列数
        long[,] dp = new long[1 << n, n];
        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = -1;
            }
        }
        
        long Dfs(int mask, int last) {
            if (System.Numerics.BitOperations.PopCount((uint)mask) == 1) {
                return 1;
            }
            
            if (dp[mask, last] != -1) {
                return dp[mask, last];
            }
            
            long res = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0 && i != last && canConnect[i, last]) {
                    res = (res + Dfs(mask ^ (1 << last), i)) % MOD;
                }
            }
            
            return dp[mask, last] = res;
        }
        
        long ans = 0;
        int fullMask = (1 << n) - 1;
        for (int i = 0; i < n; i++) {
            ans = (ans + Dfs(fullMask, i)) % MOD;
        }
        
        return (int)ans;
    }
}

var specialPerm = function(nums) {
    const MOD = 1000000007;
    const n = nums.length;
    const memo = new Map();
    
    function canAdjacent(a, b) {
        return a % b === 0 || b % a === 0;
    }
    
    function dp(mask, last) {
        if (mask === (1 << n) - 1) {
            return 1;
        }
        
        const key = (mask << 4) | last;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let result = 0;
        for (let i = 0; i < n; i++) {
            if (!(mask & (1 << i)) && (mask === 0 || canAdjacent(nums[last], nums[i]))) {
                result = (result + dp(mask | (1 << i), i)) % MOD;
            }
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dp(0, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n² × 2ⁿ)
空间复杂度O(n × 2ⁿ)

说明：

  • 时间复杂度：状态数量为 O(n × 2ⁿ)，每个状态需要枚举 n 个转移，总时间复杂度为 O(n² × 2ⁿ)
  • 空间复杂度：DP数组大小为 O(n × 2ⁿ)，预处理数组为 O(n²)，总空间复杂度为 O(n × 2ⁿ)