#638
Shopping Offers
MediumArrayDynamic ProgrammingBacktrackingBit ManipulationMemoizationBitmaskDynamic ProgrammingMemoization
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n * m^k) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n * m^k)Space O(n)
The optimal solution uses dynamic programming to efficiently calculate the minimum cost by storing results of subproblems. This avoids redundant calculations and allows us to explore offers more effectively.
⚙️
Algorithm
4 steps- 1Step 1: Create a memoization table to store the minimum cost for each combination of needs.
- 2Step 2: For each state of needs, calculate the cost without using any offers.
- 3Step 3: For each special offer, check if it can be applied and recursively calculate the cost of the remaining needs.
- 4Step 4: Store and return the minimum cost found in the memoization table.
solution.py13 lines
1def shoppingOffers(price, special, needs):
2 memo = {}
3 def dfs(needs):
4 if tuple(needs) in memo:
5 return memo[tuple(needs)]
6 total_cost = sum(needs[i] * price[i] for i in range(len(needs)))
7 for offer in special:
8 new_needs = [needs[i] - offer[i] for i in range(len(needs))]
9 if all(x >= 0 for x in new_needs):
10 total_cost = min(total_cost, offer[-1] + dfs(new_needs))
11 memo[tuple(needs)] = total_cost
12 return total_cost
13 return dfs(needs)ℹ
Complexity note: The time complexity is O(n * m^k) where n is the number of items, m is the number of offers, and k is the maximum number of times an offer can be applied. This is due to the recursive nature of the approach and memoization.
- 1Using dynamic programming can significantly reduce redundant calculations.
- 2Memoization helps in storing intermediate results to avoid recalculating costs for the same needs.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.