阿里笔试扑克牌题目 （记忆化回溯+剪枝）
阿里笔试扑克牌题目
阿里笔试扑克牌题目 （记忆化回溯+剪枝）
```python
class Main():
def __init__(self):
self.memo={}
def main(self):
lt=input().split(' ')
lt=[int(i) for i in lt]
def inter(lt,ind):
# print (lt,ind)
res=[]
if ind>=len(lt):
return 0
if lt[ind]==0 and ind==len(lt)-1:
return 0
if lt[ind]==0:
return inter(lt,ind+1)
if lt[ind]>0 and ind==len(lt)-1:
return lt[ind]
if ind+40 and lt[ind+1]>0 and lt[ind+2]>0 and lt[ind+3]>0 and lt[ind+4]>0:
# print(111)
t=lt[::]
# print ('t',t)
for i in range(ind,ind+5):
t[i]-=1
p=ind+5
for i in range(ind,ind+5):
if t[i]>0:
p=i
break
# print (t,p)
if (tuple(t),p) in self.memo:
temp=self.memo[(tuple(t),p)]
else:
temp=inter(t,p)
res.append(temp+1)
if lt[ind]>1:
# print (222)
t=lt[::]
t[ind]-=2
if t[ind]==0:
p=ind+1
else:
p=ind
# print (t, p)
if (tuple(t),p) in self.memo:
temp=self.memo[(tuple(t),p)]
else:
temp = inter(t, p)
res.append(temp + 1)
if lt[ind]>0:
# print (333)
t = lt[::]
t[ind] -= 1
if t[ind] == 0:
p = ind + 1
else:
p = ind
# print (t, p)
if (tuple(t), p) in self.memo:
temp = self.memo[(tuple(t), p)]
else:
temp = inter(t, p)
res.append(temp + 1)
# print (ind)
result=min(res)
self.memo[(tuple(lt), ind)]=result
return result
r=inter(lt,0)
print (r)
solu=Main()
solu.main()
作者：wxfnynl
