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

- There is at most 6 items and each item is at most 6, so we can use a 6 digit int as the key.
- Test every special offer. If invalid, break. We have to pay for
**EXACTLY**certain items, no more no less. - 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;
}
};
```