Minimum Number of Coins for Fruits

medium dynamic programming queue array

Problem

You are given a 0-indexed array prices where prices[i] is the coins needed to buy the (i+1)-th fruit. If you purchase the (i+1)-th fruit, you may take any number of the next i fruits for free. Even a fruit you could take for free may still be purchased to unlock its own reward. Return the minimum coins needed to acquire every fruit.

Inputprices = [3, 1, 2]

Output4

Buy fruit 1 (3 coins) → fruit 2 is free, but buying fruit 2 (1 coin) unlocks fruit 3 for free. Total = 3 + 1 = 4.

prices (comma-separated)

def minimumCoins(prices):
    n = len(prices)                          # number of fruits
    INF = float("inf")
    dp = [0] * (n + 2)                       # dp[i] uses 1-indexed fruits
    for i in range(n, 0, -1):                # fill from the last fruit back
        if 2 * i >= n:                       # buying fruit i reaches the end
            dp[i] = prices[i - 1]
        else:
            best = INF
            for j in range(i + 1, 2 * i + 2):  # next i fruits come free
                best = min(best, dp[j])      # cheapest place to resume buying
            dp[i] = prices[i - 1] + best     # pay for i, then continue
    return dp[1]                             # we must buy fruit 1 first

function minimumCoins(prices) {
  const n = prices.length;                   // number of fruits
  const INF = Infinity;
  const dp = new Array(n + 2).fill(0);       // dp[i] uses 1-indexed fruits
  for (let i = n; i >= 1; i--) {             // fill from the last fruit back
    if (2 * i >= n) {                        // buying fruit i reaches the end
      dp[i] = prices[i - 1];
    } else {
      let best = INF;
      for (let j = i + 1; j <= 2 * i + 1; j++) // next i fruits come free
        best = Math.min(best, dp[j]);        // cheapest place to resume buying
      dp[i] = prices[i - 1] + best;          // pay for i, then continue
    }
  }
  return dp[1];                              // we must buy fruit 1 first
}

int minimumCoins(int[] prices) {
    int n = prices.length;                   // number of fruits
    final int INF = Integer.MAX_VALUE;
    int[] dp = new int[n + 2];               // dp[i] uses 1-indexed fruits
    for (int i = n; i >= 1; i--) {           // fill from the last fruit back
        if (2 * i >= n) {                    // buying fruit i reaches the end
            dp[i] = prices[i - 1];
        } else {
            int best = INF;
            for (int j = i + 1; j <= 2 * i + 1; j++) // next i fruits come free
                best = Math.min(best, dp[j]); // cheapest place to resume buying
            dp[i] = prices[i - 1] + best;    // pay for i, then continue
        }
    }
    return dp[1];                            // we must buy fruit 1 first
}

int minimumCoins(vector<int>& prices) {
    int n = prices.size();                   // number of fruits
    const int INF = INT_MAX;
    vector<int> dp(n + 2, 0);                 // dp[i] uses 1-indexed fruits
    for (int i = n; i >= 1; i--) {           // fill from the last fruit back
        if (2 * i >= n) {                    // buying fruit i reaches the end
            dp[i] = prices[i - 1];
        } else {
            int best = INF;
            for (int j = i + 1; j <= 2 * i + 1; j++) // next i fruits come free
                best = min(best, dp[j]);     // cheapest place to resume buying
            dp[i] = prices[i - 1] + best;    // pay for i, then continue
        }
    }
    return dp[1];                            // we must buy fruit 1 first
}

Explanation

This is a dynamic-programming problem. Switch to 1-indexed fruits and define dp[i] as the minimum coins to acquire all fruits, assuming we buy fruit i. Buying fruit i hands us the next i fruits (indices i+1 … 2i) for free, so the very next fruit we are forced to pay for again is somewhere in i+1 … 2i+1.

That gives the recurrence dp[i] = prices[i-1] + min(dp[j]) over j in [i+1, 2i+1]. If 2i >= n the free reward already stretches past the last fruit, so nothing more must be bought and dp[i] = prices[i-1].

We fill dp from the last fruit backward so that every dp[j] we read is already finalized. The final answer is dp[1], because fruit 1 has no earlier fruit to make it free — you always have to buy it.

For prices = [3,1,2] (n = 3): dp[3] = 2, dp[2] = 1 (covers to the end), and dp[1] = 3 + min(dp[2], dp[3]) = 3 + 1 = 4.

The inner scan over the window [i+1, 2i+1] is what a monotonic queue / sliding-window minimum can speed up to O(n); here we keep the plain quadratic scan since it mirrors the recurrence directly and is easy to follow.

Time: O(n²) Space: O(n)