Loading... > https://leetcode.cn/problems/special-permutations/description/?envType=daily-question&envId=2024-05-02 对于每一个特别的排列，删除最后一个数后的排列也是特别的排列，所以这里可以用 DP 求解。 长度为 $n$ 的排列可以由长度为 $n - 1$ 的排列转移过来，但需要判断一下 $f(n)$ 最后一个数和 $f(n - 1)$ 的最后一个数是否满足取模的条件，因此转移的过程中只需要判断最后两位数即可。 因为 $n$ 的最大值为 14 ，所以我们可以使用一个 `int` 变量来记录取了哪些位置的数，取了第 $i$ 个数就将变量中第 $i$ 位置 1 ；并且需要记录每个取到的数作为最后一位时候的排列数。 这样状态转移方程就出来了：$dp[state][i] = \sum_{j \in state} dp[state \oplus (1 << i)][j]$ 。 ```c++ class Solution { public: int specialPerm(std::vector<int>& nums) { const int n = nums.size(), mod = 1e9 + 7; std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n)); for (int i = 0; i < n; i++) dp[1 << i][i] = 1; for (int state = 1; state < (1 << n); state++) { for (int i = 0; i < n; i++) { if ((state >> i & 1) == 0) continue; for (int j = 0; j < n; j++) { if (i == j || (state >> j & 1) == 0) continue; if (nums[i] % nums[j] != 0 && nums[j] % nums[i] != 0) continue; dp[state][i] = (dp[state][i] + dp[state ^ (1 << i)][j]) % mod; } } } int res = 0; for (auto &num : dp[(1 << n) - 1]) res = (res + num) % mod; return res; } }; ``` - 时间复杂度：$O(n^2 \times 2^n)$ ，其中 $n$ 为 `nums` 的长度。总共有 $n \times 2^n$ 种状态，每个状态求解的时候都需要遍历一遍 `nums` 数组，因此总时间复杂度为 $O(n^2 \times 2^n)$ 。 - 空间复杂度：$O(n \times 2^n)$ 。 最后修改：2024 年 06 月 26 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏