It's a DP solution, but cost much more time than DFS solution. The hash operation took a lot of time

```
from itertools import product, izip
class Solution(object):
def shoppingOffers(self, price, special, needs):
"""
:type price: List[int]
:type special: List[List[int]]
:type needs: List[int]
:rtype: int
"""
mul = lambda z: reduce(lambda x,y: x*(y+1), z, 1) if z else 1
sub = lambda m,n: map(lambda x,y: x-y, m, n)
needSpace = mul(needs)
map_index_group_2_index = dict(zip(product(*(xrange(x+1) for x in needs)), range(needSpace)))
self.map_index_group_2_index = map_index_group_2_index
price_list = []
for i in range(len(price)):
l = [0] * len(price)
l[i] = 1
l.append(price[i])
price_list.append(l)
dp = [1000000000]*needSpace
dp[0] = 0
for ticket in price_list + special:
buy_group = ticket[:-1]
buy_price = ticket[-1]
if not needs >= buy_group: continue
for need_group, group in izip(product(*(range(x, y+1) for x,y in zip(buy_group, needs))), product(*(range(x+1) for x in sub(needs, buy_group)))):
index = self.map_index_group_2_index[group]
if not dp[index] == 1000000000:
i = self.map_index_group_2_index[need_group]
dp[i] = min(dp[index] + buy_price, dp[i])
return dp[needSpace-1]
```