Minimum Number of Coins for Fruits
Source: leetcode
Difficulty: Medium
Tags: array, dynamic-programming, queue, heap-priority-queue, monotonic-queue

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`




C++ solution:
/*
26 18 6 12 49 7 45 45
0   1 2  3  4 5 6  7 
i = 2; j = 3 -> 2+2+1 = 2*i+1
i = 3; j = 4 -> <= 2*i+1 = 7
*/

class Solution {
public:
    int minimumCoins(vector<int>& prices) 
    {
        ios::sync_with_stdio(false); cin.tie(0);
        int n = prices.size();
        vector<int> dp(n+1, INT_MAX);
        dp[n-1] = prices[n-1];
        for (int i = n-2; i >= 0; i --)
        {
            for (int j = i+1; j <= min(n, 2*i+2); j++)
            {
                if (j == n) dp[i] = prices[i];
                else dp[i] = min(dp[i], prices[i] + dp[j]);
            }
        }
        return dp[0];
    }
};

Go solution:
func minimumCoins(prices []int) int {
    n := len(prices)
    dp := make([]int,n+1)
    for i:=0;i<n;i++{
        dp[i] = math.MaxInt
    }
    dp[n] = 0

    for i:=n-1;i>-1;i--{
        for j:=i+1;j<min(i+i+3, n+1);j++{
            dp[i] = min(dp[i], dp[j] + prices[i])
        }
    }

    return dp[0]
}

Java solution:
public class Solution {
    int[][] dp = new int[1001][1001];

    public int solve(int s, int[] v, int pow) {
        int n = v.length;
        if (s >= n)
            return 0;
        if (dp[s][pow] != -1)
            return dp[s][pow];
        if (pow == 0) {
            return v[s] + solve(s + 1, v, s + 1);
        }
        int ans = solve(s + pow, v, 0);
        for (int i = s; i <= Math.min(n - 1, s + pow - 1); i++) {
            ans = Math.min(ans, v[i] + solve(i + 1, v, i + 1));
        }
        return dp[s][pow] = ans;
    }

    public int minimumCoins(int[] v) {
        int n = v.length;
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
        int ans = solve(0, v, 0);
        return ans;
    }
}

JavaScript solution:
function minimumCoins(A) {
    let N = A.length;
    let dp = new Array(N + 5).fill(1e9);

    dp[0] = 0; // Zero coins needed to make zero sum

    // Loop through each element of the array A
    for (let i = 1; i <= N; i++) {
        let sdp = dp[i - 1] + A[i - 1]; // Sum of current dp value and current coin value

        // Loop through possible positions to update dp array
        for (let j = 0; j <= i; j++) {
            // Update dp array with the minimum value between current dp and calculated sdp
            dp[Math.min(N, i + j)] = Math.min(dp[Math.min(N, i + j)], sdp);
        }
    }

    return dp[N]; // Return the minimum coins needed for N elements
}

Python solution:
class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        prices = [0] + prices
        n = len(prices)
        if n <= 3:
            return prices[1]
        dp = [0] * n
        dp[1] = dp[2] = prices[1]
        q = deque([2])

        for i in range(3, n):
            while q and q[0] * 2 < i:
                q.popleft()

            dp[i] = dp[i - 1] + prices[i]
            if q:
                dp[i] = min(dp[i], dp[q[0] - 1] + prices[q[0]])

            while q and dp[q[-1] - 1] + prices[q[-1]] >= dp[i - 1] + prices[i]:
                q.pop()
            q.append(i)

        return dp[-1]

Ruby solution:
class SQ
    M = 1e9.to_i
    def initialize
        @l, @lm, @r, @rm = [], [M], [], M
    end
    def size = @l.size + @r.size
    def back = @r.last || @l.first
    def << x
        @r << x
        @rm = x if x < @rm
    end
    def min = [@lm.last, @rm].min
    def pop_front
        if @l.empty?
            until @r.empty?
                @l << (x = @r.pop)
                @lm << x if x <= @lm.last
            end
            @rm = M
        end
        @lm.pop if @lm.last == @l.pop
    end
end

def minimum_coins a
    q = SQ.new
    q << a.pop
    for i in (0...a.size).reverse_each
        t = i + 2
        q.pop_front while q.size > t
        q << a[i] + (q.size < t ? 0 : q.min)
    end
    q.back
end