Watch 10 video solutions for Minimum Number of Coins for Fruits, a medium level problem involving Array, Dynamic Programming, Queue. This walkthrough by NeetCode has 574,201 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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.
Example 1:
Input: prices = [3,1,2]
Output: 4
Explanation:
prices[0] = 3 coins, you are allowed to take the 2nd fruit for free.prices[1] = 1 coin, you are allowed to 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:
prices[0] = 1 coin, you are allowed to take the 2nd fruit for free.prices[2] = 1 coin, you are allowed to take the 4th fruit for free.Example 3:
Input: prices = [26,18,6,12,49,7,45,45]
Output: 39
Explanation:
prices[0] = 26 coin, you are allowed to take the 2nd fruit for free.prices[2] = 6 coin, you are allowed to take the 4th, 5th and 6th (the next three) fruits for free.prices[5] = 7 coin, you are allowed to take the 8th and 9th 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 <= 10001 <= prices[i] <= 105