# Java code using DFS with memorization

• ``````public class Solution {
List<Integer> a,c;
List<List<Integer>> b;
int n,m;
Map<Integer,Integer> map=new HashMap<>();
int hashc(List<Integer> a) //Hashcode for the needs list (we turn an state array to an integer)
{
int num=0;
for (int i=0;i<a.size();i++) num=num*10+a.get(i);
return num;
}
int dfs(List<Integer> c)
{
for (int i=0;i<n;i++) // needs<0 is illegal
if (c.get(i)<0) return 10000000;
int ha=hashc(c);
if (map.containsKey(ha)) return map.get(ha); // If we have dealt with this state before, just use our previous result (to avoid repetitive computation)
int ans=0;
for (int i=0;i<n;i++) ans+=c.get(i)*a.get(i); // buy all goods one by one
for (int i=0;i<m;i++) //use each offer
{
List<Integer> now=b.get(i);
int price=now.get(n);
for (int j=0;j<n;j++) c.set(j,c.get(j)-now.get(j));
ans=Math.min(ans,price+dfs(c));
for (int j=0;j<n;j++) c.set(j,c.get(j)+now.get(j));
}
map.put(ha,ans); //Store the result for this state
return ans;
}
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
a=price;
b=special;
n=price.size();
m=special.size();
return dfs(needs);
}
}
``````

• What is the time complexity?

• This post is deleted!

• @SanD
n^(k+1) * m * n ( n kinds of items n<=6, number of each items k<=6, m special offers m<=100)
There are only n^(k+1) different states (Quantity of every items can be 0 to 6, there are no more than 6 items), for each states, we go through each offer, the complexity is O(mn)

• I noticed the way you generate the hashcode. Pretty smart, since there are only 6 in max you need to buy for each item. But when the problem goes bigger, let's say more than 10. This "hash code" is not unique. Just a reminder. :)

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