Leetcode Problem 2431. Maximize Total Tastiness of Purchased Fruits

2431. Maximize Total Tastiness of Purchased Fruits

Leetcode Solutions

Dynamic Programming with Memoization

  1. Initialize a 3D array dp with dimensions [n][maxAmount + 1][maxCoupons + 1] to -1, representing uncomputed states.
  2. Define a recursive function dfs(i, budget, coup) that returns the maximum tastiness from the i-th fruit to the last fruit, given the remaining budget and coup coupons.
  3. If i is equal to the length of the price array, return 0 as the base case.
  4. If the state dp[i][budget][coup] is already computed, return its value to avoid recomputation.
  5. Recursively call dfs(i + 1, budget, coup) to get the maximum tastiness if we skip the i-th fruit.
  6. If the budget allows, recursively call dfs(i + 1, budget - price[i], coup) and add tastiness[i] to get the maximum tastiness if we buy the i-th fruit without a coupon.
  7. If the budget allows and we have coupons left, recursively call dfs(i + 1, budget - price[i] // 2, coup - 1) and add tastiness[i] to get the maximum tastiness if we buy the i-th fruit with a coupon.
  8. Take the maximum of the three options and store it in dp[i][budget][coup].
  9. Return dp[i][budget][coup].
  10. Call dfs(0, maxAmount, maxCoupons) to start the recursion from the first fruit.
UML Thumbnail

Iterative Dynamic Programming

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...