# Bit manipulation and memoized DFS

• Since number of each item is <= 6 and there are at most 6 kind of items, 3 * 6 = 18 bits should be enough.

``````class Solution {
public:
const int INF = 1000000000;
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
// 4MB memory
vector<int> state(1 << 3 * price.size(), 1000000000);
state[0] = 0;
vector<pair<int, int>> costs;
for (int i = 0; i < price.size(); i++) {
}
for (int i = 0; i < special.size(); ++i) {
int tmp = 0;
int offset = 0;
int total = 0;
for (int j = 0; j < price.size(); ++j) {
tmp += (special[i][j] << offset);
total += price[j] * special[i][j];
offset += 3;
}
// Promos are not necessarily cheaper
state[tmp] = min(special[i].back(), total);
costs.push_back({tmp, special[i].back()});
}
int target = 0;
int offset = 0;
for (int i = 0; i < needs.size(); i++) {
target += (needs[i] << offset);
offset += 3;
}
return helper(costs, state, target);
}
private:
int helper(vector<pair<int, int>>& costs, vector<int>& state, int target) {
if (state[target] != 1000000000) {
return state[target];
}
for (auto p: costs) {
int s = p.first;
bool valid = true;
int cur = target;
while (cur || s) {
if ((cur & 7) < (s & 7)) {
valid = false;
break;
}
cur >>= 3;
s >>= 3;
}
if (!valid)
continue;
state[target] = min(state[target], helper(costs, state, target - p.first) + p.second);
}
return state[target];
}
};
``````

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