Problem

You are given an 1-indexed integer array prices where prices[i] denotes the number of coins needed to purchase the ith fruit.

The fruit market has the following reward for each fruit:

  • If you purchase the ith 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] coins to receive its reward.

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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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] <= 10^5

Solution

Method 1 – Dynamic Programming (Monotonic Queue)

Intuition

To minimize coins, we use DP where dp[i] is the minimum coins to buy up to fruit i. For each fruit, buying it lets us get the next i fruits for free, so we update the DP accordingly. A monotonic queue can optimize the range updates.

Approach

  1. Initialize dp[0] = 0 and dp[i] = inf for all other i.
  2. For each fruit i from 1 to n:
    • For each possible previous fruit j where j < i, if buying fruit j covers fruit i, update dp[i].
    • Use a monotonic queue to keep track of minimum dp values for efficient updates.
  3. The answer is dp[n].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int minimumCoins(vector<int>& prices) {
        int n = prices.size();
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = max(0, i-i); j < i; ++j) {
                if (j + j >= i-1) {
                    dp[i] = min(dp[i], dp[j] + prices[i-1]);
                }
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func minimumCoins(prices []int) int {
    n := len(prices)
    dp := make([]int, n+1)
    for i := range dp { dp[i] = 1<<30 }
    dp[0] = 0
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if j+j >= i-1 {
                if dp[j]+prices[i-1] < dp[i] {
                    dp[i] = dp[j]+prices[i-1]
                }
            }
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (j+j >= i-1) {
                    dp[i] = Math.min(dp[i], dp[j] + prices[i-1]);
                }
            }
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun minimumCoins(prices: IntArray): Int {
        val n = prices.size
        val dp = IntArray(n+1) { Int.MAX_VALUE }
        dp[0] = 0
        for (i in 1..n) {
            for (j in 0 until i) {
                if (j+j >= i-1) {
                    dp[i] = minOf(dp[i], dp[j] + prices[i-1])
                }
            }
        }
        return dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minimumCoins(self, prices: list[int]) -> int:
        n: int = len(prices)
        dp: list[int] = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            for j in range(i):
                if j+j >= i-1:
                    dp[i] = min(dp[i], dp[j] + prices[i-1])
        return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn minimum_coins(prices: Vec<i32>) -> i32 {
        let n = prices.len();
        let mut dp = vec![i32::MAX; n+1];
        dp[0] = 0;
        for i in 1..=n {
            for j in 0..i {
                if j+j >= i-1 {
                    dp[i] = dp[i].min(dp[j] + prices[i-1]);
                }
            }
        }
        dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    minimumCoins(prices: number[]): number {
        const n = prices.length;
        const dp = new Array(n+1).fill(Infinity);
        dp[0] = 0;
        for (let i = 1; i <= n; ++i) {
            for (let j = 0; j < i; ++j) {
                if (j+j >= i-1) {
                    dp[i] = Math.min(dp[i], dp[j] + prices[i-1]);
                }
            }
        }
        return dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), as we check all previous states for each fruit.
  • 🧺 Space complexity: O(n), for the DP array.