526. 优美的排列

526. 优美的排列

这题目看见求数量，就习以为常的觉得是一个动态规划的题目，结果看题解是一个回溯的题目。
该题有点类似于求全排列数量或者所有情况的题目。主要特点就是：

• 没被排列的所有数都会出现在这个位置。
  所以常规的解法就是采用一个used的数组
• 另外一个特征出口一定要想好，我刚开始做的时候就是没写出空这特殊情况。一般考虑的就是所有数都排列好的特殊情况或者只剩一个。视情况而定，这里是所有排列好，全排列求数量的时候只剩最后一个

方法一：DFS + 爆搜

class Solution {
    public int countArrangement(int n) {
        return getCount(n, 1, new boolean[n+1]);
    }

    public int getCount(int n, int i, boolean[] used) {
        if (i > n) {
            return 1;
        }
        int count = 0;
        for(int j = 1; j<=n; j++) {
            if(!used[j] && (j%i==0 || i%j==0)) {
                used[j] = true;
                count += getCount(n, i+1, used);
                used[j] = false;
            }
        }
        return count;
    }
}