<div>
Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:
perm[i]is divisible byi.iis divisible byperm[i].
Given an integer n, return the number of the beautiful arrangements that you can construct.
Example 1:
<pre>Input: n = 2 Output: 2 Explanation: The first beautiful arrangement is [1,2]: - perm[1] = 1 is divisible by i = 1 - perm[2] = 2 is divisible by i = 2 The second beautiful arrangement is [2,1]: - perm[1] = 2 is divisible by i = 1 - i = 2 is divisible by perm[2] = 1 </pre>
Example 2:
<pre>Input: n = 1 Output: 1 </pre>
Constraints:
1 <= n <= 15
</div>
题目大意：
求数组中所有排列中下标（从1开始）和数值能整除（下标整除数值或反之）的个数
解题思路：
一开始考虑用DP，因为求个数且类似于L368 Largest Divisible Subset，但问题与子问题的具体排位有关，所以DP不可行。考虑用Stack，但数组顺序可变。
只能用暴力法，也就是DFS中排列求解
解题步骤：
N/A
注意事项：
- 用排列模板，但此题不涉及具体数组。用set来记录访问过的数值而不是下标，start来记录模拟结果path中的位置
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18def countArrangement(self, n: int) -> int:
return self.permute(n, 1, set())
def permute(self, n, start, visited): # 2, 1, [F,F,F]
if start == n + 1: # remember n + 1
#print(path)
return 1
res = 0 # 1
for i in range(1, n + 1): # [1,3)
if i in visited:
continue
if i % start == 0 or start % i == 0:
visited.add(i)
#path.append(i)
res += self.permute(n, start + 1, visited) # 2, 2, [FFT]
#path.pop()
visited.remove(i)
return res
算法分析：
时间复杂度为O(解大小)，空间复杂度O(n)
