# Python recursion + DP 66ms

• Save the pre-computed the result globally and reuse.

``````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 = 0
for j in xrange(len(X)):
if X[j] % i == 0 or i % X[j] == 0:
total += helper(i - 1, X[:j] + X[j + 1:])
cache[key] = total
return helper(N, tuple(range(1, N + 1)))
``````

• No need for `cache[(i - 1, tmp)] = c`. The call `helper(i - 1, tmp)` has already cached its result.

Rewritten a bit:

``````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 helper(N, tuple(range(1, N + 1)))
``````

• @StefanPochmann Yeah, you are totally right! Thanks

• @zhongyuan9817 @StefanPochmann Why is "i" included in key? Isn't "i" just len(X)?

• This post is deleted!

• @nkstnkst Same question, but I think you're right!

• @zhongyuan9817 @StefanPochmann Why is "i" included in key?

I don't know, that's from @zhongyuan9817 :-P

I guess I didn't think that much when I modified the code. You're right, it's just `len(X)` and not needed.

• Could anyone can provide Java version with dfs+cache?
thanks

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.