# Python DP solution, can't believe beating 98%.

• ``````class Solution(object):
def __init__(self):
preRequisites = {1:{4:2,64:8,256:16},2:{128:16},
4:{1:2,64:16,256:32},8:{32:16},32:{8:16},
64:{1:8,4:16,256:128},128:{2:16},
256:{64:128,1:16,4:32}}
digits2nums,num2count,self.digits2counts = {i:[] for i in xrange(1,10)},{(1<<i):{(1<<i):1} for i in xrange(9)},{1:9}
for i in xrange(1,512):
n,digits = i,0
while n>0:
digits += 1
n -= n&(-n)
digits2nums[digits].append(i)
for digits in xrange(2,10):
self.digits2counts[digits] = 0
for num in digits2nums[digits]:
num2count[num],n = {},num
while n>0:
last = n&(-n)
preNum,num2count[num][last] = num^last,0
nn = preNum
while nn>0:
preLast = nn&(-nn)
if preLast in preRequisites and last in preRequisites[preLast]:
if preRequisites[preLast][last]&preNum>0:
num2count[num][last] += num2count[preNum][preLast]
else:
num2count[num][last] += num2count[preNum][preLast]
nn -= preLast
self.digits2counts[digits] += num2count[num][last]
n -= last

def numberOfPatterns(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
ans = 0
for i in xrange(m,n+1):
ans += self.digits2counts[i]
return ans
``````

A little bit explanation:

We can use numbers from 0 to 511 to represent which keys in a pattern have been passed. e.g. 111100111(487) means keys 1,2,3,6,7,8,9 have been passed.

Another important thing is for each key, which one is the last key passed in this pattern. e.g. when we consider 111100111(487) with the last key to be 9, we have to consider 011100111(231) with the last key being 1,2,3,6,7,8 respectively. Among them if the last key of 231 is 1, then it's impossible because 5 has not been passed.

Therefore in the DP table we record the number of patters corresponding to:

1. The number representing which keys have been passed.
2. The last passed key among those keys.

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