题目描述：

LeetCode 526. Beautiful Arrangement

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the i_th position (1 ≤ i ≤ N) in this array:

1. The number at the i_th position is divisible by i.
2. i is divisible by the number at the i_th position.

Now given N, how many beautiful arrangements can you construct?

Example 1:

Input: 2
Output: 2
Explanation: 

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Note:

1. N is a positive integer and will not exceed 15.

题目大意：

如果整数1到N的排列，第i个数满足下列规则之一，则称该排列为“美丽排列”

1. 第i个位置的数字可以被i整除
2. i可以被第i个位置的数字整除

给定数字N，求有多少个美丽排列

注意：N是正整数并且不超过15

解题思路：

记忆化搜索（Memoization）

搜索函数定义为：solve(idx, nums)

其中idx为当前数字的下标，nums为剩余待选数字

初始令idx = 1, nums = [1 .. N]

遍历nums，记当前数字为n，除n以外的其余元素为nums'

若n满足题设的整除条件，则将solve(idx + 1, nums')累加至答案

Python代码：

class Solution(object):
    def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
        cache = dict()
        def solve(idx, nums):
            if not nums: return 1
            key = idx, tuple(nums)
            if key in cache: return cache[key]
            ans = 0
            for i, n in enumerate(nums):
                if n % idx == 0 or idx % n == 0:
                    ans += solve(idx + 1, nums[:i] + nums[i+1:])
            cache[key] = ans
            return ans
        return solve(1, range(1, N + 1))

 

本文链接：http://bookshadow.com/weblog/2017/02/19/leetcode-beautiful-arrangement/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码