# Minimum Number of Coins for Fruits
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-coins-for-fruits)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-coins-for-fruits
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Heap (Priority Queue), Queue, Monotonic Queue
---
## Problem
You are given an **0-indexed** integer array `prices` where `prices[i]` denotes the number of coins needed to purchase the `(i + 1)th` fruit.

The fruit market has the following reward for each fruit:

* If you purchase the `(i + 1)th` fruit at `prices[i]` coins, you can get any number of the next `i` fruits for free.

**Note** that even if you **can** take fruit `j` for free, you can still purchase it for `prices[j - 1]` coins to receive its reward.

Return the **minimum** number of coins needed to acquire all the fruits.

**Example 1:**

**Input:** prices = \[3,1,2\]

**Output:** 4

**Explanation:**

* Purchase the 1st fruit with `prices[0] = 3` coins, you are allowed to take the 2nd fruit for free.
* Purchase the 2nd fruit with `prices[1] = 1` coin, you are allowed to take the 3rd fruit for free.
* Take the 3rd fruit for free.

Note that even though you could take the 2nd fruit for free as a reward of buying 1st fruit, you purchase it to receive its reward, which is more optimal.

**Example 2:**

**Input:** prices = \[1,10,1,1\]

**Output:** 2

**Explanation:**

* Purchase the 1st fruit with `prices[0] = 1` coin, you are allowed to take the 2nd fruit for free.
* Take the 2nd fruit for free.
* Purchase the 3rd fruit for `prices[2] = 1` coin, you are allowed to take the 4th fruit for free.
* Take the 4th fruit for free.

**Example 3:**

**Input:** prices = \[26,18,6,12,49,7,45,45\]

**Output:** 39

**Explanation:**

* Purchase the 1st fruit with `prices[0] = 26` coin, you are allowed to take the 2nd fruit for free.
* Take the 2nd fruit for free.
* Purchase the 3rd fruit for `prices[2] = 6` coin, you are allowed to take the 4th, 5th and 6th (the next three) fruits for free.
* Take the 4th fruit for free.
* Take the 5th fruit for free.
* Purchase the 6th fruit with `prices[5] = 7` coin, you are allowed to take the 8th and 9th fruit for free.
* Take the 7th fruit for free.
* Take the 8th fruit for free.

Note that even though you could take the 6th fruit for free as a reward of buying 3rd fruit, you purchase it to receive its reward, which is more optimal.

**Constraints:**

* `1 <= prices.length <= 1000`
* `1 <= prices[i] <= 105`

# Approaches
## Bottom-Up Dynamic Programming
This problem exhibits optimal substructure and overlapping subproblems, making it a good candidate for dynamic programming. We can define a DP state `dp[i]` as the minimum cost to acquire the first `i` fruits. Our goal is to find `dp[n]`, the minimum cost for all `n` fruits.

The base case is `dp[0] = 0`, as acquiring no fruits costs nothing.

To compute `dp[i]`, we must ensure fruit `i` is acquired. This can happen if we buy fruit `i`, or if we get it for free from a prior purchase. We can generalize this by considering that to acquire fruit `i`, we must have bought some fruit `k` (where `1 <= k <= i`) that 'covers' fruit `i`. Buying fruit `k` (at index `k-1`) gives fruits `k+1` through `2k` for free. Thus, fruit `k` covers fruit `i` if `k=i` or `k+1 <= i <= 2k`. The latter condition simplifies to `ceil(i/2) <= k <= i-1`.

So, to find `dp[i]`, we can take the minimum over all valid choices of `k` from `ceil(i/2)` to `i`. For each such `k`, the cost is the price of fruit `k` (`prices[k-1]`) plus the minimum cost to acquire fruits `1` to `k-1` (`dp[k-1]`). This gives the recurrence relation:

`dp[i] = min_{k=ceil(i/2)}^{i} (dp[k-1] + prices[k-1])`

We can implement this by iterating `i` from 1 to `n` and, for each `i`, iterating `k` through its valid range to find the minimum cost.
**Time:** O(n^2) - We have a nested loop structure. The outer loop runs `n` times (for `i` from 1 to `n`), and the inner loop runs up to `i/2` times (for `k` from `ceil(i/2)` to `i`). This results in a total time complexity proportional to the sum of `i/2` from `i=1` to `n`, which is `O(n^2)`. · **Space:** O(n) - We use a DP array of size `n+1` to store the minimum costs.
**Pros:** Relatively straightforward to understand and implement based on the DP recurrence relation.; Correctly solves the problem for the given constraints.
**Cons:** The time complexity is quadratic, which can be slow for larger constraints (though it passes for n=1000).
### Explanation
We use a bottom-up dynamic programming approach. Let `dp[i]` be the minimum cost to obtain the first `i` fruits (using 1-based indexing for fruits, so `i` ranges from 1 to `n`). The size of our `dp` array will be `n+1`.

- **Initialization**: `dp[0] = 0`. All other `dp` values can be initialized to infinity.

- **Recurrence**: To calculate `dp[i]`, we consider all possible fruits `k` we could have purchased that would cover fruit `i`. A purchase of fruit `k` covers fruit `i` if `i` is `k` itself, or if `i` is one of the free fruits obtained from buying `k` (i.e., `k+1 <= i <= 2k`). This gives a range for `k` from `ceil(i/2)` to `i`. For any such `k`, the total cost would be the cost to acquire fruits up to `k-1` (`dp[k-1]`) plus the cost of fruit `k` (`prices[k-1]`). We take the minimum over all these possibilities.

`dp[i] = min(dp[k-1] + prices[k-1])` for `k` in `[ceil(i/2), i]`

- **Final Answer**: The minimum cost to acquire all `n` fruits is `dp[n]`.

Here is the Java implementation:
```java
class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n + 1];
        // dp[i] = min cost to acquire first i fruits (1-based index)
        
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            // To acquire fruit i, we must buy some fruit k (1-based)
            // such that buying k covers i.
            // This means k=i, or k+1 <= i <= 2k.
            // The range for k is [ceil(i/2), i].
            // For positive integers, ceil(i/2) is (i+1)/2 using integer division.
            int start_k = (i + 1) / 2;
            for (int k = start_k; k <= i; k++) {
                // Cost of buying fruit k is prices[k-1].
                // We must have acquired fruits 1...k-1, which costs dp[k-1].
                // Total cost for this choice is dp[k-1] + prices[k-1].
                dp[i] = Math.min(dp[i], dp[k - 1] + prices[k - 1]);
            }
        }
        
        return dp[n];
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n+1`, where `n` is the number of fruits.
- Initialize `dp[0] = 0`, and other elements to a large value.
- Iterate `i` from 1 to `n` to compute `dp[i]`, the minimum cost to acquire fruits `1` through `i`.
- For each `i`, calculate the cost by considering all possible fruits `k` (from `ceil(i/2)` to `i`) that could be purchased to cover fruit `i`.
- The cost of purchasing fruit `k` is `prices[k-1]`, and we must have already acquired fruits `1` to `k-1` with a minimum cost of `dp[k-1]`. The total cost for this choice is `dp[k-1] + prices[k-1]`.
- Update `dp[i]` with the minimum cost found among all valid choices of `k`.
- The final answer is `dp[n]`.

## Optimized DP with Sliding Window Minimum (Deque)
The `O(n^2)` DP approach can be optimized by observing the nature of the recurrence relation:
`dp[i] = min_{k=ceil(i/2)}^{i} (dp[k-1] + prices[k-1])`

Let's define a cost function `cost(k) = dp[k-1] + prices[k-1]`. The problem then becomes finding the minimum value of `cost(k)` in a window `[ceil(i/2), i]`. As we increment `i`, this window slides and expands. This is a classic sliding window minimum problem, which can be solved efficiently in linear time using a double-ended queue (deque).

The deque will store indices `k` from the current window. It will be maintained in two ways: the indices themselves will be in increasing order, and their corresponding `cost(k)` values will also be in increasing order. This structure allows us to find the minimum `cost(k)` in the window (which will always be at the front of the deque) in `O(1)` time.

For each step `i`, we first remove indices from the front of the deque that are no longer in the current window. Then, we find `dp[i]` by comparing the minimum from the deque with the cost of buying fruit `i`. Finally, we add `i` to the deque, maintaining the sorted-cost property by removing any elements from the back that have a higher or equal cost.
**Time:** O(n) - The main loop runs `n` times. Each index `i` is added to and removed from the deque at most once. Therefore, all operations inside the loop take amortized `O(1)` time, leading to a total linear time complexity. · **Space:** O(n) - We use a DP array of size `n+1` and a deque that can store up to `n` indices in the worst case.
**Pros:** Highly efficient with a linear time complexity.; Optimal solution for the problem.
**Cons:** The implementation is more complex than the basic DP approach.; Requires knowledge of the sliding window minimum technique using a deque.
### Explanation
This approach optimizes the `O(n^2)` DP solution to `O(n)` time using a deque to maintain the sliding window minimum.

- **DP State**: `dp[i]` is the minimum cost to acquire fruits `1...i`.
- **Optimization**: The calculation `dp[i] = min_{k=ceil(i/2)}^{i} (dp[k-1] + prices[k-1])` is a range minimum query. We use a deque to find this minimum in amortized `O(1)` time.

**Algorithm Steps:**
1. Initialize `dp` array of size `n+1` with `dp[0] = 0`.
2. Initialize an empty `ArrayDeque` to store indices `k`.
3. Loop `i` from 1 to `n`:
    a. Define the window start `start_k = (i + 1) / 2`.
    b. Remove indices from the deque's front that are less than `start_k`.
    c. Get the minimum cost from the window `[start_k, i-1]`. This corresponds to `cost(deque.peekFirst())` if the deque is not empty.
    d. Calculate the cost for buying fruit `i`: `cost(i) = dp[i-1] + prices[i-1]`.
    e. `dp[i]` is the minimum of the costs from steps c and d.
    f. To add `i` to the deque, first remove indices from the back of the deque whose associated cost is greater than or equal to `cost(i)`. Then, add `i` to the back.
4. Return `dp[n]`.

Here is the Java implementation:
```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n + 1];
        // Deque stores indices k (1-based) for the sliding window minimum.
        Deque<Integer> deque = new ArrayDeque<>();
        
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            int start_k = (i + 1) / 2;
            
            // Remove indices from the front that are out of the window [start_k, i].
            while (!deque.isEmpty() && deque.peekFirst() < start_k) {
                deque.pollFirst();
            }
            
            // Cost from buying a fruit j in [start_k, i-1]
            int minPrevCost = Integer.MAX_VALUE;
            if (!deque.isEmpty()) {
                int k = deque.peekFirst();
                minPrevCost = dp[k - 1] + prices[k - 1];
            }
            
            // Cost from buying fruit i itself.
            int costOfBuyingI = dp[i - 1] + prices[i - 1];
            
            dp[i] = Math.min(minPrevCost, costOfBuyingI);
            
            // Add current index i to the deque, maintaining the increasing cost property.
            while (!deque.isEmpty()) {
                int k = deque.peekLast();
                if (dp[k - 1] + prices[k - 1] >= costOfBuyingI) {
                    deque.pollLast();
                } else {
                    break;
                }
            }
            deque.offerLast(i);
        }
        
        return dp[n];
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n+1` and a deque.
- Initialize `dp[0] = 0`.
- Iterate `i` from 1 to `n`.
- In each iteration, first, prune the deque by removing indices `k` from the front that are no longer in the current window `[ceil(i/2), i]`.
- The minimum cost from the choices `k` in `[ceil(i/2), i-1]` can be found in O(1) from the front of the deque.
- Calculate the cost for choosing `k=i`, which is `dp[i-1] + prices[i-1]`.
- `dp[i]` is the minimum of these two options.
- Finally, add `i` to the deque, maintaining the property that costs associated with indices in the deque are monotonically increasing. This may involve removing elements from the back.
- The result is `dp[n]`.

# Solutions
### Java

```java
class Solution {
private
  int[] prices;
private
  int[] f;
private
  int n;
public
  int minimumCoins(int[] prices) {
    n = prices.length;
    f = new int[n + 1];
    this.prices = prices;
    return dfs(1);
  }
private
  int dfs(int i) {
    if (i * 2 >= n) {
      return prices[i - 1];
    }
    if (f[i] == 0) {
      f[i] = 1 << 30;
      for (int j = i + 1; j <= i * 2 + 1; ++j) {
        f[i] = Math.min(f[i], prices[i - 1] + dfs(j));
      }
    }
    return f[i];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumCoins(vector<int> &prices) {
    int n = prices.size();
    int f[n + 1];
    memset(f, 0x3f, sizeof(f));
    function<int(int)> dfs = [&](int i) {
      if (i * 2 >= n) {
        return prices[i - 1];
      }
      if (f[i] == 0x3f3f3f3f) {
        for (int j = i + 1; j <= i * 2 + 1; ++j) {
          f[i] = min(f[i], prices[i - 1] + dfs(j));
        }
      }
      return f[i];
    };
    return dfs(1);
  }
};

```

### Python

```python
class Solution:
    def minimumCoins(self, prices: List[int]) -> int: @ cache def dfs(i: int) -> int: if i * 2 >= len(prices): return prices[i - 1] return prices[i - 1] + min(dfs(j) for j in range(i + 1, i * 2 + 2)) return dfs(1)

```