C++, DP/DFS with Memoization


  • 5
    Z

    The idea is to try every special offer using DFS, and memorize intermediate results, which is one type of DP.

    1. There is at most 6 items and each item is at most 6, so we can use a 6 digit int as the key.
    2. Test every special offer. If invalid, break. We have to pay for EXACTLY certain items, no more no less.
    3. Greedy doesn't work. One example is [3, 2], [[1, 2, 4] [2, 1, 5]], [6, 6]. We need 2 first offers and 2 second offers. Greedy would choose 3 first offers.
    class Solution {
    public:
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
            // memorize intermediate results 
            unordered_map<int, int> mp;
            return helper(price, special, mp, get_key(needs));
        }
    private:
        int helper(vector<int>& price, vector<vector<int>>& special, unordered_map<int, int>& mp, int k) {
            if (mp.count(k)) return mp[k];
            int n = price.size(), ans = 0;
            // pows is to help get each digit of key
            vector<int> pows(n, 1);
            for (int i = n-2; i >= 0; i--) pows[i] = pows[i+1]*10;
            for (int i = 0; i < n; i++) ans += ((k/pows[i])%10)*price[i];
            for (auto spe:special) {
                int key = 0, i = 0;
                // check whether this offer is valid
                while (i < n) {
                    int t = (k/pows[i])%10;
                    if (t >= spe[i]) 
                        key = key*10+(t-spe[i++]);
                    else
                        break;
                } 
                if (i == n) ans = min(ans, spe[n]+helper(price, special, mp, key));
            }
            mp[k] = ans;
            return ans;
        }
        int get_key(vector<int>& needs) {
            int n = needs.size(), key = 0;
            for (int i = n-1, p = 1; i >= 0; i--, p *= 10)
                key += needs[i]*p;
            return key;
        }
    };
    

  • 0
    W
    This post is deleted!

Log in to reply
 

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