526.md

526 Beautiful Arrangement

Description

link

---

Solution

• 设置helper函数，目的是求出在当前位置是i的情况下，有X内的数字能得到多少中beautiful arrangement
• 在Backtrack的过程中，每当有一个j满足条件的话，就可以求i-1的位置了，把j从x中去掉
• 使用cache来保存已经计算过的(i, x)
• 初始化x是1-N的Tuple（Tuple也可以用index索引）

---

Code

Complexity O(N^2)

cache = {}
class Solution(object):
    def countArrangement(self, N):
        def helper(i, X):
            if i == 1:
                return 1
            key = i, X
            if key in cache:
                return cache[key]
            total = sum(helper(i - 1, X[:j] + X[j + 1:])
                        for j, x in enumerate(X)
                        if x % i == 0 or i % x == 0)
            cache[key] = total
            return total
        return helper(N, tuple(range(1, N + 1)))