Watch 2 video solutions for Maximize Total Tastiness of Purchased Fruits, a medium level problem involving Array, Dynamic Programming. This walkthrough by Programming Live with Larry has 249 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two non-negative integer arrays price and tastiness, both arrays have the same length n. You are also given two non-negative integers maxAmount and maxCoupons.
For every integer i in range [0, n - 1]:
price[i] describes the price of ith fruit.tastiness[i] describes the tastiness of ith fruit.You want to purchase some fruits such that total tastiness is maximized and the total price does not exceed maxAmount.
Additionally, you can use a coupon to purchase fruit for half of its price (rounded down to the closest integer). You can use at most maxCoupons of such coupons.
Return the maximum total tastiness that can be purchased.
Note that:
Example 1:
Input: price = [10,20,20], tastiness = [5,8,8], maxAmount = 20, maxCoupons = 1 Output: 13 Explanation: It is possible to make total tastiness 13 in following way: - Buy first fruit without coupon, so that total price = 0 + 10 and total tastiness = 0 + 5. - Buy second fruit with coupon, so that total price = 10 + 10 and total tastiness = 5 + 8. - Do not buy third fruit, so that total price = 20 and total tastiness = 13. It can be proven that 13 is the maximum total tastiness that can be obtained.
Example 2:
Input: price = [10,15,7], tastiness = [5,8,20], maxAmount = 10, maxCoupons = 2 Output: 28 Explanation: It is possible to make total tastiness 20 in following way: - Do not buy first fruit, so that total price = 0 and total tastiness = 0. - Buy second fruit with coupon, so that total price = 0 + 7 and total tastiness = 0 + 8. - Buy third fruit with coupon, so that total price = 7 + 3 and total tastiness = 8 + 20. It can be proven that 28 is the maximum total tastiness that can be obtained.
Constraints:
n == price.length == tastiness.length1 <= n <= 1000 <= price[i], tastiness[i], maxAmount <= 10000 <= maxCoupons <= 5Problem Overview: You are given arrays price and tastiness. Each fruit can be purchased normally or with a coupon that halves its price. With a fixed budget and limited coupons, the goal is to maximize the total tastiness of the fruits you buy.
Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)
Try every decision for each fruit: skip it, buy it at full price, or buy it using a coupon. The recursion explores all combinations while tracking remaining budget and coupons. This guarantees the optimal result but quickly becomes impractical because the number of states grows exponentially. It mainly helps understand the decision structure before applying dynamic programming.
Approach 2: Memoization Search (Top-Down DP) (O(n * amount * coupons) time, O(n * amount * coupons) space)
Cache the recursive states to avoid recomputation. The state can be represented as dfs(i, remainingAmount, remainingCoupons), meaning the maximum tastiness achievable starting from fruit i with the given budget and coupons left. For each fruit, consider three options: skip it, buy it at full price if affordable, or buy it using a coupon if coupons remain. Store results in a memo table so repeated states return instantly. This converts the exponential search into a manageable DP solution. The technique is a classic combination of dynamic programming and array traversal.
Approach 3: Bottom-Up Knapsack DP (O(n * amount * coupons) time, O(n * amount * coupons) space)
This problem can also be modeled as a 3D knapsack-style DP. Build a table where dp[i][a][c] represents the best tastiness using the first i fruits with budget a and c coupons. Transition by skipping the fruit, buying it normally, or buying it with a coupon. While the complexity matches the memoized version, the iterative formulation is sometimes easier to reason about for knapsack-style interview problems.
Recommended for interviews: The memoized DFS solution is usually the clearest. It directly models the decision tree and demonstrates strong understanding of dynamic programming state design. Explaining the brute-force recursion first shows you understand the search space, while the memoized version shows optimization skills expected in a medium-level interview problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(2^n) | O(n) | Conceptual baseline to understand all purchase choices |
| Memoization Search (Top-Down DP) | O(n * amount * coupons) | O(n * amount * coupons) | General optimal solution; avoids recomputation with cached states |
| Bottom-Up Knapsack DP | O(n * amount * coupons) | O(n * amount * coupons) | When you prefer iterative DP tables over recursion |