<p>You are given an integer array <code>prices</code> where <code>prices[i]</code> denotes the number of coins needed to purchase the <code>i<sup>th</sup></code> fruit.</p>

<p>The fruit market has the following reward for each fruit:</p>

<ul>
	<li>If you purchase the <code>i<sup>th</sup></code> fruit at <code>prices[i]</code> coins, you can get any number of the next <code>(i + 1)</code> fruits for free.</li>
</ul>

<p><strong>Note</strong> that even if you <strong>can</strong> take fruit <code>j</code> for free, you can still purchase it for <code>prices[j]</code> coins to receive its reward.</p>

<p>Return the <strong>minimum</strong> number of coins needed to acquire all the fruits.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">prices = [3,1,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Purchase the 1<sup>st</sup> fruit with <code>prices[0] = 3</code> coins, you are allowed to take the 2<sup>nd</sup> fruit for free.</li>
	<li>Purchase the 2<sup>nd</sup> fruit with <code>prices[1] = 1</code> coin, you are allowed to take the 3<sup>rd</sup> fruit for free.</li>
	<li>Take the 3<sup>rd</sup> fruit for free.</li>
</ul>

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

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">prices = [1,10,1,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Purchase the 1<sup>st</sup> fruit with <code>prices[0] = 1</code> coin, you are allowed to take the 2<sup>nd</sup> fruit for free.</li>
	<li>Take the 2<sup>nd</sup> fruit for free.</li>
	<li>Purchase the 3<sup>rd</sup> fruit for <code>prices[2] = 1</code> coin, you are allowed to take the 4<sup>th</sup> fruit for free.</li>
	<li>Take the 4<sup>t</sup><sup>h</sup> fruit for free.</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">prices = [26,18,6,12,49,7,45,45]</span></p>

<p><strong>Output:</strong> <span class="example-io">39</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Purchase the 1<sup>st</sup> fruit with <code>prices[0] = 26</code> coin, you are allowed to take the 2<sup>nd</sup> fruit for free.</li>
	<li>Take the 2<sup>nd</sup> fruit for free.</li>
	<li>Purchase the 3<sup>rd</sup> fruit for <code>prices[2] = 6</code> coin, you are allowed to take the 4<sup>th</sup>, 5<sup>th</sup> and 6<sup>th</sup> (the next three) fruits for free.</li>
	<li>Take the 4<sup>t</sup><sup>h</sup> fruit for free.</li>
	<li>Take the 5<sup>t</sup><sup>h</sup> fruit for free.</li>
	<li>Purchase the 6<sup>th</sup> fruit with <code>prices[5] = 7</code> coin, you are allowed to take the 8<sup>th</sup> and 9<sup>th</sup> fruit for free.</li>
	<li>Take the 7<sup>t</sup><sup>h</sup> fruit for free.</li>
	<li>Take the 8<sup>t</sup><sup>h</sup> fruit for free.</li>
</ul>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= prices.length &lt;= 1000</code></li>
	<li><code>1 &lt;= prices[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    # def minimumCoins(self, prices: List[int]) -> int:
# we always purchase the first fruit. we know we can get the next i=0+1 ONE fruit for free
# @ the i=1 fruit, we know we can get the next i=1+1 = TWO fruits for free IF WE BUY the i = 1 fruit. We know we need to acquire all fruits (either for free or by buying)
# scenarios
        # [a, b BOUGHT, could be free, could be free] ->
            #  [a, b BOUGHT, c GOT FOR FREE, d BOUGHT, ...]
            #  [a, b BOUGHT, c BOUGHT, d GOT FOR FREE, ...]
            #  [a, b BOUGHT, c GOT FOR FREE, d GOT FOR FREE, e MUST BUY, ...]
        # [a, b GOT FOR FREE, c could buy, d could buy] ->
            #  [a, b GOT FOR FREE, c BOUGHT, free but could buy (if buy, coverage = next 3+1 fruits), free but could buy (if buy, coverage = next 4+1 fruits), free but could buy (if buy, coverage = next 5+1 fruits), ...]
# There is a difference between actually cannot buy and and getting for free. We cannot buy if it is out of our range. We can get for free if it is INSIDE our range. our range = i+1 aka arr[i+1:i+i] i.e. i=4's range is i=5,6,7,8
# we want to make sure whatever fruit we BUY results in the smallest possible current cost
# prices[26,18,6,12,49,7,45,45]
# we have to buy at 26. we can either buy at 18 and get 18's range for free or get 18 for free and buy the fruit after it (i+1)
# (potentialSum = 26+18, range=[i=1+1 : i+i=1+1])
# (potentialSum = 26+(fruit[i]+1)), range=[i+1+1:i+1+i+1]) we must buy
# when there is a range, we recurse on that range
    def helper(self, prices, i, dp, limit):
        if i >= len(prices):
            return 0
        if dp[i][limit] != -1:
            return dp[i][limit]
        else:
            li = min(len(prices)-1,(i + i + 1))
            pick = self.helper(prices, i + 1, dp, li) + prices[i]
            nonPick = float('inf')
            if limit >= i:
                nonPick = self.helper(prices, i + 1, dp, limit)
            dp[i][limit] = min(pick, nonPick)
            return dp[i][limit]

    def minimumCoins(self, prices) -> int:
        dp = [[-1 for i in range(len(prices))] for i in range(len(prices))]
        i = 0
        limit = -1
        return self.helper(prices, i, dp, limit)

    #     minHeap =[(prices[0]+0,0,0,(0,1))]
    #     heapq.heapify(minHeap)
    #     while minHeap:
    #         # i is the current price we are on
    #         arr = []
    #         while len(minHeap)>=2 and minHeap[0][0] == minHeap[1][0] and minHeap[1][2] > minHeap[0][2]:
    #             # if there are multiple SAME potential sums, we want to use the tuple with the FURTHEST INDEX bc we want to be done as fast as we can
    #             arr.append(heappop(minHeap))
            
    #         potentialSum, sm, i, rnge = heappop(minHeap)
    #         # potentialSum is the POTENTIAL sum that we are organizing our minHeap by. we want to constantly use the tuple with the minimum POTENTIAL sum, and then actually add to it 

    #         # print((potentialSum,sm,i,rnge), "heap:", minHeap)
    #         if rnge[1] >= len(prices)-1:
    #             return sm + prices[i]

    #         # we buy the current fruit
    #         sm += prices[i]

    # # when we buy it, we want to add the potential sums that come from when:
    #     # we buy a number in the range
    #     # we buy the number right AFTER its range ends, signiifying that we got ALL its range for free/we did not buy any numbers in the range = we move to the number after range done
    #         for j in range(rnge[0],rnge[1]+2):
    #             if j < len(prices) and j != 0:
    #                 # print("aDDING,",prices[j], "for i = ",j)
    #                 tup = (prices[j]+sm, sm, j, (j+1,j+j+1))
    #                 if tup not in minHeap:
    #                     heappush(minHeap,tup)
            
    #         for a in arr:
    #             heappush(minHeap,a)
28000