LeetCode 2431 - Maximize Total Tastiness of Purchased Fruits

This problem asks us to maximize the total tastiness of fruits we purchase while staying within a fixed budget. Each fruit has two attributes: a price and a tastiness value. We may either skip a fruit or buy it, but each fruit can only be purchased once.

leetcodemediumarraydynamic-programming

LeetCode Problem 2431

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to maximize the total tastiness of fruits we purchase while staying within a fixed budget. Each fruit has two attributes: a price and a tastiness value. We may either skip a fruit or buy it, but each fruit can only be purchased once.

There is an additional twist: we are allowed to use coupons. A coupon reduces the cost of a fruit to half of its original price, rounded down. However, there is a limited number of coupons available, and each coupon can only be used on one fruit.

The goal is to select a subset of fruits, deciding for each purchased fruit whether to use a coupon or not, so that:

  1. The total money spent does not exceed maxAmount.
  2. The number of coupons used does not exceed maxCoupons.
  3. The sum of tastiness values is maximized.

The input consists of:

  • price[i], the purchase cost of the i-th fruit.
  • tastiness[i], the tastiness score of the i-th fruit.
  • maxAmount, the maximum total budget.
  • maxCoupons, the maximum number of coupons available.

The output is a single integer representing the maximum total tastiness achievable under these constraints.

The constraints tell us a lot about the expected solution:

  • n <= 100, meaning we can afford polynomial-time dynamic programming.
  • maxAmount <= 1000, which suggests a budget-based DP is feasible.
  • maxCoupons <= 5, which is very small and strongly hints that coupon count should be part of the DP state.

A brute-force solution that explores every buying possibility would be far too expensive because each fruit has three choices:

  • Skip it
  • Buy normally
  • Buy with a coupon

That leads to roughly 3^n possibilities, which is impossible for n = 100.

Some important edge cases include fruits with zero price, fruits with zero tastiness, situations where no purchase is affordable, and cases where coupons dramatically change affordability. We also must correctly handle integer division because coupon discounts use floor division.

Approaches

Brute Force

A straightforward approach is to try every possible decision for every fruit.

For each fruit, we have three options:

  1. Skip it.
  2. Buy it normally.
  3. Buy it using a coupon.

We recursively explore every combination while tracking:

  • Remaining budget
  • Remaining coupons
  • Total tastiness accumulated

This guarantees correctness because every valid purchasing combination is considered, and we simply take the maximum tastiness among all feasible states.

However, the number of possibilities grows exponentially. Since each fruit has roughly three choices, the total complexity becomes approximately O(3^n). With n = 100, this is completely infeasible.

Optimal Approach, Dynamic Programming

The key observation is that many recursive states repeat.

Suppose we are at fruit index i, with remaining budget money, and coupons left. The best answer from this state does not depend on how we arrived there, only on these three values.

This overlapping-subproblem structure makes dynamic programming a perfect fit.

We define a DP state:

dp(i, remainingAmount, remainingCoupons)

This represents the maximum tastiness obtainable starting from fruit i.

At each fruit, we consider three possibilities:

  • Skip the fruit.
  • Buy normally if affordable.
  • Buy with a coupon if affordable and coupons remain.

Since there are only:

  • n <= 100
  • maxAmount <= 1000
  • maxCoupons <= 5

The total number of states is manageable.

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n) O(n) Explores every purchase combination
Optimal O(n × maxAmount × maxCoupons) O(n × maxAmount × maxCoupons) Memoized DP over index, budget, and coupons

Algorithm Walkthrough

We use top-down dynamic programming with memoization.

  1. Define a recursive function dfs(index, remaining_amount, remaining_coupons).

This function returns the maximum tastiness we can still obtain starting from index, given the remaining budget and coupons. 2. Handle the base case.

If index == n, there are no fruits left to process, so the answer is 0. 3. Consider skipping the current fruit.

We always have the option not to buy a fruit. This gives:

dfs(index + 1, remaining_amount, remaining_coupons)
  1. Consider buying normally.

If the fruit price is affordable:

price[index] <= remaining_amount

then we can buy it and gain its tastiness:

tastiness[index] +
dfs(index + 1,
    remaining_amount - price[index],
    remaining_coupons)
  1. Consider buying with a coupon.

If we still have coupons available:

remaining_coupons > 0

we compute the discounted price:

discounted_price = price[index] // 2

If affordable, we take:

tastiness[index] +
dfs(index + 1,
    remaining_amount - discounted_price,
    remaining_coupons - 1)
  1. Take the maximum among all valid choices.

Since we want maximum tastiness, we choose the best outcome. 7. Use memoization.

Without memoization, the same state would be recomputed many times. Caching ensures each state is solved once.

Why it works

The algorithm works because of optimal substructure. For any fruit index and remaining resources, the optimal answer depends only on the best decision among the three valid actions at that fruit. Since every state is solved optimally and memoized, the recursion explores all valid purchase plans exactly once per state, guaranteeing the globally optimal tastiness.

Python Solution

from functools import lru_cache
from typing import List

class Solution:
    def maxTastiness(
        self,
        price: List[int],
        tastiness: List[int],
        maxAmount: int,
        maxCoupons: int
    ) -> int:
        n = len(price)

        @lru_cache(None)
        def dfs(
            index: int,
            remaining_amount: int,
            remaining_coupons: int
        ) -> int:
            if index == n:
                return 0

            # Option 1: Skip this fruit
            best = dfs(
                index + 1,
                remaining_amount,
                remaining_coupons
            )

            # Option 2: Buy normally
            normal_price = price[index]
            if normal_price <= remaining_amount:
                best = max(
                    best,
                    tastiness[index] + dfs(
                        index + 1,
                        remaining_amount - normal_price,
                        remaining_coupons
                    )
                )

            # Option 3: Buy with coupon
            if remaining_coupons > 0:
                discounted_price = price[index] // 2

                if discounted_price <= remaining_amount:
                    best = max(
                        best,
                        tastiness[index] + dfs(
                            index + 1,
                            remaining_amount - discounted_price,
                            remaining_coupons - 1
                        )
                    )

            return best

        return dfs(0, maxAmount, maxCoupons)

The implementation follows the algorithm directly.

We first store the number of fruits in n. Then we define a memoized recursive function using @lru_cache(None) so repeated states are computed only once.

Each recursive call represents a state defined by:

  • Current fruit index
  • Remaining budget
  • Remaining coupons

The function first considers skipping the fruit because this choice is always valid.

Next, it checks whether buying the fruit normally is affordable. If so, it adds the fruit's tastiness and recursively computes the best remaining result.

Then it considers the coupon option. The discounted price is calculated using floor division (// 2), exactly matching the problem statement. We also ensure at least one coupon remains before attempting this transition.

Finally, the function returns the maximum tastiness among all valid choices. The initial call starts from the first fruit with full budget and all coupons available.

Go Solution

func maxTastiness(price []int, tastiness []int, maxAmount int, maxCoupons int) int {
	n := len(price)

	memo := make(map[[3]int]int)

	var dfs func(int, int, int) int

	dfs = func(index int, remainingAmount int, remainingCoupons int) int {
		if index == n {
			return 0
		}

		key := [3]int{index, remainingAmount, remainingCoupons}

		if value, exists := memo[key]; exists {
			return value
		}

		// Option 1: Skip this fruit
		best := dfs(index+1, remainingAmount, remainingCoupons)

		// Option 2: Buy normally
		if price[index] <= remainingAmount {
			candidate := tastiness[index] + dfs(
				index+1,
				remainingAmount-price[index],
				remainingCoupons,
			)

			if candidate > best {
				best = candidate
			}
		}

		// Option 3: Buy with coupon
		if remainingCoupons > 0 {
			discountedPrice := price[index] / 2

			if discountedPrice <= remainingAmount {
				candidate := tastiness[index] + dfs(
					index+1,
					remainingAmount-discountedPrice,
					remainingCoupons-1,
				)

				if candidate > best {
					best = candidate
				}
			}
		}

		memo[key] = best
		return best
	}

	return dfs(0, maxAmount, maxCoupons)
}

The Go solution follows the same memoized recursion pattern as Python. Since Go does not have a built-in memoization decorator like lru_cache, we explicitly store computed states in a map.

The memoization key is a fixed-size array of three integers:

[index, remainingAmount, remainingCoupons]

This works efficiently because arrays are comparable and can be used as map keys.

Integer division in Go naturally performs floor division for integers, so:

price[index] / 2

correctly matches the coupon behavior.

Go slices are used for price and tastiness, and there is no special handling required for nil versus empty slices because the problem guarantees valid input lengths.

Worked Examples

Example 1

price = [10,20,20]
tastiness = [5,8,8]
maxAmount = 20
maxCoupons = 1

We begin at:

dfs(0, 20, 1)
State Decision Result
(0,20,1) Skip fruit 0 Explore future
(0,20,1) Buy normally Cost = 10, tastiness = 5
(0,20,1) Buy with coupon Cost = 5, tastiness = 5

Following the best path:

Fruit Action Cost Total Cost Tastiness
Fruit 0 Buy normally 10 10 5
Fruit 1 Use coupon 10 20 13
Fruit 2 Skip 0 20 13

Final answer:

13

Example 2

price = [10,15,7]
tastiness = [5,8,20]
maxAmount = 10
maxCoupons = 2

Starting state:

dfs(0, 10, 2)

Best sequence:

Fruit Action Cost Total Cost Tastiness
Fruit 0 Skip 0 0 0
Fruit 1 Coupon 7 7 8
Fruit 2 Coupon 3 10 28

Final answer:

28

The DP explores every valid decision path but memoization ensures repeated states are reused instead of recomputed.

Complexity Analysis

Measure Complexity Explanation
Time O(n × maxAmount × maxCoupons) Each DP state is computed once
Space O(n × maxAmount × maxCoupons) Memoization table plus recursion stack

The state space is bounded by:

n × (maxAmount + 1) × (maxCoupons + 1)

For each state, we perform constant work because only three transitions are considered: skip, normal purchase, and coupon purchase.

Given the constraints:

100 × 1001 × 6 ≈ 600,600

the solution runs comfortably within limits.

Test Cases

solution = Solution()

# Provided examples
assert solution.maxTastiness(
    [10, 20, 20],
    [5, 8, 8],
    20,
    1
) == 13  # Example 1

assert solution.maxTastiness(
    [10, 15, 7],
    [5, 8, 20],
    10,
    2
) == 28  # Example 2

# Single fruit, affordable
assert solution.maxTastiness(
    [5],
    [10],
    5,
    0
) == 10  # Buy normally

# Single fruit, only affordable with coupon
assert solution.maxTastiness(
    [10],
    [50],
    5,
    1
) == 50  # Coupon makes purchase possible

# Cannot afford anything
assert solution.maxTastiness(
    [100, 200],
    [10, 20],
    10,
    0
) == 0  # No valid purchase

# Zero budget
assert solution.maxTastiness(
    [1, 2, 3],
    [5, 6, 7],
    0,
    5
) == 0  # No purchases possible

# Free fruits
assert solution.maxTastiness(
    [0, 0],
    [5, 10],
    0,
    0
) == 15  # Free items should be taken

# Coupon choice matters
assert solution.maxTastiness(
    [10, 8],
    [50, 20],
    10,
    1
) == 70  # Coupon best used on expensive fruit

# Multiple coupon possibilities
assert solution.maxTastiness(
    [8, 9, 10],
    [10, 20, 30],
    10,
    2
) == 50  # Best combination uses coupons strategically

# Zero tastiness fruits
assert solution.maxTastiness(
    [5, 5],
    [0, 10],
    10,
    0
) == 10  # Ignore useless fruit

# Large coupon count
assert solution.maxTastiness(
    [10, 20, 30],
    [10, 20, 30],
    30,
    5
) == 60  # Enough coupons to buy all
Test Why
Example 1 Validates standard purchase plus coupon usage
Example 2 Validates multiple coupon use
Single affordable fruit Simplest positive case
Coupon-only affordability Ensures coupon transition works
Cannot afford anything Verifies returning zero
Zero budget Boundary condition
Free fruits Ensures zero-cost items work
Coupon choice matters Confirms optimal coupon allocation
Multiple coupon possibilities Tests strategic DP decisions
Zero tastiness fruits Ensures useless items are skipped
Large coupon count Verifies handling excess coupons

Edge Cases

Zero Budget

When maxAmount = 0, a naive implementation might incorrectly attempt purchases or fail to consider free fruits. Our implementation correctly prevents purchases unless the effective price, including coupon discount, is zero. Since affordability is always checked before transitions, invalid purchases never occur.

Coupon Makes an Expensive Fruit Affordable

A fruit may be impossible to buy normally but affordable after applying a coupon. For example:

price = [10]
budget = 5
coupon = 1

Since 10 // 2 = 5, the fruit becomes purchasable. A buggy implementation might only consider normal prices or mishandle floor division. Our solution explicitly computes:

price[i] // 2

before checking affordability.

Strategic Coupon Allocation

The best solution is not always achieved by using coupons immediately. Sometimes saving a coupon for a later expensive fruit yields higher tastiness. Since the DP explores all valid choices at every fruit, including skipping coupon use, it naturally finds the globally optimal allocation.

Zero Price Fruits

Some fruits may already cost 0. Since each fruit can only be purchased once, an incorrect implementation could accidentally reuse them infinitely in a poorly designed DP. Our state always advances the index:

index + 1

ensuring each fruit is processed exactly once.