Задача: 638. Shopping Offers Сложность: medium В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите. Пример: Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2] Output: 14 👨‍💻 Алгоритм: 1⃣Рекурсивное вычисление стоимости: Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя динамическое программирование для запоминания уже вычисленных значений. 2⃣Использование специальных предложений: Для каждой комбинации товаров в специальных предложениях, определите, можно ли использовать это предложение без превышения нужд. Если можно, вычислите новую стоимость, учитывая это предложение. 3⃣Выбор минимальной стоимости: Сравните стоимость при использовании специальных предложений и стоимость при покупке товаров по индивидуальным ценам, выбирая минимальную стоимость. 😎 Решение: class Solution { public: int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) { unordered_map<string, int> memo; return dfs(price, special, needs, memo); } private: int dfs(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, unordered_map<string, int>& memo) { string key = serialize(needs); if (memo.find(key) != memo.end()) { return memo[key]; } int minPrice = 0; for (int i = 0; i < needs.size(); i++) { minPrice += needs[i] * price[i]; } for (vector<int>& offer : special) { vector<int> newNeeds(needs.size()); bool valid = true; for (int i = 0; i < needs.size(); i++) { if (needs[i] < offer[i]) { valid = false; break; } newNeeds[i] = needs[i] - offer[i]; } if (valid) { minPrice = min(minPrice, offer.back() + dfs(price, special, newNeeds, memo)); } } memo[key] = minPrice; return minPrice; } string serialize(vector<int>& needs) { string key = ""; for (int need : needs) { key += to_string(need) + ","; } return key; } }; Ставь 👍 и забирай 📚 Базу знаний