Java code using DFS with memorization


  • 2
    K
    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);
        }
    }
    

  • 0
    S

    What is the time complexity?


  • 0
    K
    This post is deleted!

  • 0
    K

    @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)


  • 0

    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. :)


Log in to reply
 

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