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

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🍔 目录

• • 🚩 题目链接
  • ⛲ 题目描述
  • 🌟 求解思路&实现代码&运行结果
  • • ⚡ 递归 + 记忆化搜索 + 动态规划
    • • 🥦 求解思路
      • 🥦 实现代码
      • 🥦 运行结果
  • 💬 共勉

🚩 题目链接

• 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

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

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

🥦 求解思路

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

🥦 运行结果

💬 共勉