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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/**
 * Find the lowest price to buy exactly certain items with optimal use of special offers.
 * Recursion with Memoization approach.
 *
 * @param {number[]} price - Array of prices for each item
 * @param {number[][]} special - Array of special offers
 * @param {number[]} needs - Array of needed quantities for each item
 * @return {number} - Lowest price
 */
function shoppingOffers(price, special, needs) {
  // Memoization map to store results of subproblems
  const memo = new Map();
 
  /**
   * Helper function to calculate the minimum price for the current needs.
   *
   * @param {number[]} currentNeeds - Current needed quantities
   * @return {number} - Minimum price
   */
  function dfs(currentNeeds) {
    // Convert currentNeeds to a string for memoization
    const key = currentNeeds.toString();
 
    // If we've already computed the result for this state, return it
    if (memo.has(key)) {
      return memo.get(key);
    }
 
    // Option 1: Buy all items at their regular prices
    let result = 0;
    for (let i = 0; i < currentNeeds.length; i++) {
      result += currentNeeds[i] * price[i];
    }
 
    // Option 2: Use a special offer
    for (const offer of special) {
      // Check if the offer is valid
      let valid = true;
      for (let i = 0; i < currentNeeds.length; i++) {
        if (currentNeeds[i] < offer[i]) {
          valid = false;
          break;
        }
      }
 
      if (valid) {
        // Update the needs
        const newNeeds = [...currentNeeds];
        for (let i = 0; i < currentNeeds.length; i++) {
          newNeeds[i] -= offer[i];
        }
 
        // Recursively solve the problem for the updated needs
        const offerPrice = offer[offer.length - 1];
        result = Math.min(result, offerPrice + dfs(newNeeds));
      }
    }
 
    // Memoize and return the result
    memo.set(key, result);
    return result;
  }
 
  return dfs(needs);
}
 
/**
 * Find the lowest price to buy exactly certain items with optimal use of special offers.
 * Dynamic Programming approach.
 *
 * @param {number[]} price - Array of prices for each item
 * @param {number[][]} special - Array of special offers
 * @param {number[]} needs - Array of needed quantities for each item
 * @return {number} - Lowest price
 */
function shoppingOffersDP(price, special, needs) {
  // DP map to store results of subproblems
  const dp = new Map();
 
  /**
   * Helper function to calculate the minimum price for the current needs.
   *
   * @param {number[]} currentNeeds - Current needed quantities
   * @return {number} - Minimum price
   */
  function solve(currentNeeds) {
    // Convert currentNeeds to a string for memoization
    const key = currentNeeds.toString();
 
    // If we've already computed the result for this state, return it
    if (dp.has(key)) {
      return dp.get(key);
    }
 
    // Option 1: Buy all items at their regular prices
    let result = 0;
    for (let i = 0; i < currentNeeds.length; i++) {
      result += currentNeeds[i] * price[i];
    }
 
    // Option 2: Use a special offer
    for (const offer of special) {
      // Check if the offer is valid
      let valid = true;
      for (let i = 0; i < currentNeeds.length; i++) {
        if (currentNeeds[i] < offer[i]) {
          valid = false;
          break;
        }
      }
 
      if (valid) {
        // Update the needs
        const newNeeds = [...currentNeeds];
        for (let i = 0; i < currentNeeds.length; i++) {
          newNeeds[i] -= offer[i];
        }
 
        // Recursively solve the problem for the updated needs
        const offerPrice = offer[offer.length - 1];
        result = Math.min(result, offerPrice + solve(newNeeds));
      }
    }
 
    // Store the result in the DP table
    dp.set(key, result);
    return result;
  }
 
  return solve(needs);
}
 
// Test cases
console.log(shoppingOffers([2, 5], [[3, 0, 5], [1, 2, 10]], [3, 2]));  // 14
console.log(shoppingOffers([2, 3, 4], [[1, 1, 0, 4], [2, 2, 1, 9]], [1, 2, 1]));  // 11
console.log(shoppingOffers([2, 3, 4], [[1, 1, 0, 4], [2, 2, 1, 9]], [0, 0, 0]));  // 0
 
console.log(shoppingOffersDP([2, 5], [[3, 0, 5], [1, 2, 10]], [3, 2]));  // 14
console.log(shoppingOffersDP([2, 3, 4], [[1, 1, 0, 4], [2, 2, 1, 9]], [1, 2, 1]));  // 11
console.log(shoppingOffersDP([2, 3, 4], [[1, 1, 0, 4], [2, 2, 1, 9]], [0, 0, 0]));  // 0