1
/** https://leetcode.com/problems/shopping-offers/
2
 * @param {number[]} price
3
 * @param {number[][]} special
4
 * @param {number[]} needs
5
 * @return {number}
6
 */
7
var shoppingOffers = function (price, special, needs) {
8
  // Memoization
9
  this.map = new Map();
10

11
  return shop(price, special, needs);
12
};
13

14
var shop = function (price, special, needs) {
15
  // Return memoization result
16
  if (this.map.has(needs) === true) {
17
    return this.map.get(needs);
18
  }
19

20
  // Calculate total if purchase without special offers
21
  let currTotal = calcTotal(price, needs);
22

23
  // Try every single offers
24
  for (let i = 0; i < special.length; i++) {
25
    // Check special offer can be used
26
    if (canUseSpecial(special[i], needs) === true) {
27
      // Clone the `needs` because we don't want to modify the original `needs`, update the `needs` count by calling `useSpecial()`
28
      let cloneNeeds = [...needs];
29
      cloneNeeds = useSpecial(special[i], cloneNeeds);
30

31
      // Count total if using special offers, basically repeat the same process with updated `needs`
32
      let totalUsingSpecial =
33
        special[i][needs.length] + shop(price, special, cloneNeeds);
34

35
      // Compare the `currTotal` with total if using special offers
36
      currTotal = Math.min(currTotal, totalUsingSpecial);
37
    }
38
  }
39

40
  // Update memoization and return result
41
  this.map.set(needs, currTotal);
42
  return currTotal;
43
};
44

45
var calcTotal = function (price, needs) {
46
  // Calculate total if purchase without special offers, basically `price[i] * needs[i]`
47
  let out = 0;
48

49
  for (let i = 0; i < price.length; i++) {
50
    out += price[i] * needs[i];
51
  }
52

53
  return out;
54
};
55

56
var canUseSpecial = function (special, needs) {
57
  // Check if special offers can be used, if any of `special[i]` is more than `needs[i]`, the special can not be used, return false because we can not buy more than needed
58
  for (let i = 0; i < needs.length; i++) {
59
    if (needs[i] < special[i]) {
60
      return false;
61
    }
62
  }
63

64
  return true;
65
};
66

67
var useSpecial = function (special, needs) {
68
  // Update the `needs` count by subtracting it from `special`
69
  for (let i = 0; i < needs.length; i++) {
70
    needs[i] -= special[i];
71
  }
72

73
  return needs;
74
};