# C++, DP/DFS with Memoization

• 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;
}
};
``````

• This post is deleted!

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