2741、特别的排列

leetcode 数组动态规划位运算状态压缩

Created At : 2024-06-27 21:53

Count:916 Views 👀 :

分析
1. 示例 1：
2. 示例 2：
分析
1. 递归+记忆化
2. 动态规划

分析

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

对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。
请你返回特别排列的总数目，由于答案可能很大，请将它对 109 + 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 表示未被选取
0 表示被选取

递归+记忆化

描述：

辅助递归变量，标记那些元素被取过了
记忆化数组，并初始化
枚举每个元素开始的
- 特殊排列的情况，累加 dfs。右移异或
  - 标记状态到达 0，说明所有元素都已经访问
  - 标记状态分支已被记忆化，返回记忆化的结果
  - 继续递归，处理子问题
    - 对于没有拿取（左移且）的元素，继续递归（右移异或），统计子序列的特别排列的数量
取模运算，返回结果

public class Solution {
    public int specialPerm(int[] nums) {
        int n = nums.length;
        int u = (1 << n) - 1;// 标记当前需要判断的元素数量
        long[][] memo = new long[u][n];
        for (long[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }
        long ans = 0;
        // 对于每个元素执行dfs，累加每一结果
        for (int i = 0; i < n; i++) {
            ans += dfs(u ^ (1 << i), i, nums, memo);
        }
        // 返回结果
        return (int) (ans % 1_000_000_007);
    }

    private long dfs(int s, int i, int[] nums, long[][] memo) {
        if (s == 0) {
            return 1; // 找到一个特别排列
        }
        if (memo[s][i] != -1) { // 之前计算过
            return memo[s][i];
        }
        long res = 0;
        for (int j = 0; j < nums.length; j++) {
            // 满足条件后继续执行，dfs，不选重复元素
            if ((s >> j & 1) > 0 && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                res += dfs(s ^ (1 << j), j, nums, memo);
            }
        }
        return memo[s][i] = res; // 记忆化
    }
}

动态规划

将递推翻译成动态规划。

动规状态数组：$f[S][i]$ 表示下标集合位S，上一个选的数的下标是i时的，可以构造出排列的数量。

状态转移：
$$
f[S][i] = \sum_{j \in S}f[S \backslash {j}][j]
$$S

由于是不铜元素的排列，无须考虑重复排列，只需进行枚举。

public class Solution {
    public int specialPerm(int[] nums) {
        int n = nums.length;
        int u = (1 << n) - 1;
        long[][] f = new long[u][n];
        // 初始化 排列数
        Arrays.fill(f[0], 1L);
        for (int s = 1; s < u; s++) {
            for (int i = 0; i < n; i++) {
                if ((s >> i & 1) != 0) {// 已经枚举过了，跳过
                    continue;
                }
                for (int j = 0; j < n; j++) {
                    // 每一被枚举过 且 满足排列条件
                    if ((s >> j & 1) != 0 && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                        f[s][i] += f[s ^ (1 << j)][j];
                    }
                }
            }
        }

        // 累加排列数量
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += f[u ^ (1 << i)][i];
        }
        return (int) (ans % 1_000_000_007);
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com