【LeetCode:2741. 特别的排列 + 递归 + 记忆化搜索 + 动态规划】_其他编程

在这里插入图片描述

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

🚩 题目链接

2741. 特别的排列

⛲ 题目描述

给你一个下标从 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] <= 109

🌟 求解思路&实现代码&运行结果

⚡ 递归 + 记忆化搜索 + 动态规划

🥦 求解思路

我们设计这样一个递归函数，如果dfs(i,cnt)，i表示选择的上一个位置的下标，cnt代表此时选择了多少个数字，由此进行递归。不出意外，时间会超时。
在此基础上改进缓存，我们发现，答案错误，也就是这俩个变量并不能覆盖表示所有的情况，为什么呢？因为原递归方法中我们结合了flag数组来标记之前被选择的情况。
那么怎么求解呢？想一个方法替换flag，通过一个变量来记录之前选择过的下标情况即可。

🥦 实现代码

class solution {

    int[] nums;
    int n;
    boolean[] flag;
    hashmap<string, integer> map;

    public int specialperm(int[] nums) {
        this.nums = nums;
        n = nums.length;
        flag = new boolean[n];
        map = new hashmap<>();
        int cnt = process(0, -1, 0);
        return cnt % 1000000007;
    }

    public int process(int depth, int prevpos, int status) {
        if (depth == n) {
            return 1;
        }
        string key = prevpos + "#" + status;
        if (map.containskey(key)) {
            return map.get(key);
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!flag[i]) {
                // 第0个数不需要考虑是否满足条件
                if (prevpos == -1) {
                    flag[i] = true;
                    res = (res + process(depth + 1, i, status | (1 << i))) % 1000000007;
                    flag[i] = false;
                } else if (nums[prevpos] % nums[i] == 0 || nums[i] % nums[prevpos] == 0) {
                    flag[i] = true;
                    res = (res + process(depth + 1, i, status | (1 << i))) % 1000000007;
                    flag[i] = false;
                }
            }
        }
        map.put(key, res);
        return res;
    }
}