Sponsored
Sponsored
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] <= 105NeetCode