友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
526. 优美的排列
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
-
perm[i]能够被i整除 -
i能够被perm[i]整除
给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
示例 1：
输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
- perm[1] = 1 能被 i = 1 整除
- perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
- perm[1] = 2 能被 i = 1 整除
- i = 2 能被 perm[2] = 1 整除
示例 2：
输入：n = 1 输出：1
提示：
-
1 <= n <= 15
思路分析
以为是有条件的全排列，没想到是动态规划。还是有些懵逼，还要再体会一下。
官方题解中，先找出每个坐标可选的数字，然后再进行回溯也是一个不错的解法。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-02-27 19:19:47
*/
public int countArrangement(int n) {
return dfs(0, n);
}
private int dfs(int s, int n) {
if (s == ((1 << n) - 1)) {
return 1;
}
int result = 0;
int i = Integer.bitCount(s) + 1;
for (int j = 1; j <= n; j++) {
if ((s >> (j - 1) & 1) == 0 && (i % j == 0 || j % i == 0)) {
result += dfs(s | (1 << (j - 1)), n);
}
}
return result;
}