-
Notifications
You must be signed in to change notification settings - Fork 4
/
0638-shopping-offers.cpp
31 lines (30 loc) · 1.02 KB
/
0638-shopping-offers.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
unordered_map<string, int> map;
int dot(vector<int> &needs, vector<int> price){
int sum = 0;
for(int i = 0; i < needs.size(); i++)
sum += needs[i] * price[i];
return sum;
}
int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs){
string key;
for (int n: needs) key += to_string(n);
if (map.count(key)) return map[key];
int j = 0, res = dot(needs, price);
for (auto s: special) {
vector<int> clone = needs;
for (j = 0; j < needs.size(); j++) {
int diff = clone[j] - s[j];
if (diff < 0) break;
clone[j] = diff;
}
if (j == needs.size())
res = min(res, s[j] + shopping(price, special, clone));
}
return map[key] = res;
}
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
return shopping(price, special, needs);
}
};