The idea is very easy.

Note:`state`

is `keyArr[]`

which represents the number of each item left to be bought.

It is just like backpack problem, for each `state`

, we need to check whether an offer is available, if it is available:

- The price of using this offer is less than not using it. Then we should implement this offer. Update the final result if needed. Update the
`state`

after using this offer in the map. Put the new`state`

in the queue. - The price of using this offer is not less than not using it. Discard it.

The above process is `BFS`

process.

The `DP`

part is to record the old value of each `state`

which has already been calculated, just like memorization method.

Since we need to overwrite `equals`

function if we use array to be the key of map, I use `encode`

and `decode`

to record each `state`

.

The only implicit assumption is that for each `state`

, if we can use an offer, then this offer must save money.

`Complexity`

: For this certain problem, the key point is the number of offers due to the limit of types and number of items.

To fill in the map, the worst case is the multiplication of all numbers of items. For example, if we have 6 items and the number of each item is 6, then there are 6^6 blank to be filled in.

The only part to use the number of offer is the DFS part, so the time complexity of the algorithm is approximately `O(number of items)`

^ x * `O(number of offers)`

. If we can neglect the number of items, it is `O(n)`

, where `n`

is the number of offers.

```
public class Solution {
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int n = price.size();
if (n == 0) {
return 0;
}
int[] keyArr = new int[n];
HashMap<String, Integer> map = new HashMap<>();
int sum = 0;
for (int i = 0; i < needs.size(); i++) {
keyArr[i] = needs.get(i);
sum += price.get(i) * needs.get(i);
}
map.put(encode(keyArr), sum);
Queue<String> q = new LinkedList<>();
q.offer(encode(keyArr));
int res = sum;
while (q.size() > 0){
int size = q.size();
for (int i = 0; i < size; i++){
String key = q.poll();
for (List<Integer> offer : special){
keyArr = decode(key);
if (validOffer(keyArr, offer)){
int currPrice = map.get(key) + offer.get(offer.size()-1);
for (int j = 0; j < keyArr.length; j++){
keyArr[j] -= offer.get(j);
currPrice -= offer.get(j) * price.get(j);
}
String newKey = encode(keyArr);
int originalPrice = map.getOrDefault(newKey, Integer.MAX_VALUE);
if (originalPrice > currPrice){
map.put(newKey, currPrice);
res = Math.min(res, currPrice);
q.offer(newKey);
}
}
}
}
}
return res;
}
private String encode(int[] keyArr) {
StringBuilder key = new StringBuilder();
for (int i : keyArr){
key.append(i);
}
return key.toString();
}
private int[] decode(String key){
int[] keyArr = new int[key.length()];
for (int i = 0; i < key.length(); i++){
keyArr[i] = key.charAt(i) - '0';
}
return keyArr;
}
private boolean validOffer(int[] keyArr, List<Integer> offer){
for (int i = 0; i < keyArr.length; i++){
if (offer.get(i) > keyArr[i]){
return false;
}
}
return true;
}
}
```