Leetcode Problem 638. Shopping Offers

638. Shopping Offers

Leetcode Solutions

Approach # Using Recursion with Memoization

  1. Define a recursive function shopping(price, special, needs, memo) that returns the minimum cost to satisfy the needs.
  2. If the current needs state is in the memo hashmap, return the stored result.
  3. Initialize res with the cost of buying items at regular prices without any special offers.
  4. Iterate over each offer in the special list.
  5. For each offer, create a clone of the current needs.
  6. Check if the offer is valid (i.e., it does not require more items than the current needs).
  7. If valid, apply the offer by subtracting the offer quantities from the clone needs.
  8. Recursively call shopping(price, special, clone, memo) to compute the cost after applying the offer.
  9. Update res with the minimum of its current value and the cost of the offer plus the recursive call result.
  10. Store the computed minimum cost for the current needs state in the memo hashmap.
  11. Return res as the minimum cost for the current needs state.
UML Thumbnail

Approach # Using Simple Recursion

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...