[LeetCode]Beautiful Arrangement 作者是 在线疯狂 发布于 2017年2月19日 在 LeetCode.

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 ith position (1 ≤ i ≤ N) in this array:

1. The number at the ith position is divisible by i.
2. i is divisible by the number at the ith 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. 第i个位置的数字可以被i整除
2. i可以被第i个位置的数字整除

解题思路：

```搜索函数定义为：solve(idx, 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))
``````

Pingbacks已关闭。

1. juzi 发布于 2017年2月25日 01:49 #

我觉得这里并没有Memoization, 这里的key从1 到N 被依次计算，不会有hit cache提前return的时候，是我哪里理解有错么？

2. 在线疯狂 发布于 2017年2月25日 11:39 #

不妨用一个小型测试用例，输出并观察key和nums，可以帮助理解。