Problem Description
You are given an array of prices where prices[i] is the cost for the (i+1)th fruit. When you buy the (i+1)th fruit for prices[i] coins, you obtain a reward: you may take any number of the next (up to i+1) fruits free of charge. (Note that even if a fruit can be taken for free as a reward, you may choose to purchase it in order to receive its own reward.) Return the minimum number of coins needed to acquire all the fruits.
Key Insights
- The decision at each fruit is whether to purchase it (incurring its cost but obtaining a reward) or, if possible, allow it to be taken free as part of an earlier reward.
- When you purchase fruit i (0-indexed), you can choose how many fruits immediately following it to take for free, up to (i+1) fruits.
- The free fruits do not give you their reward. Thus, sometimes it may be beneficial to “skip” a free opportunity and purchase a fruit to get an even larger reward.
- A dynamic programming approach can be used where dp[i] represents the minimum cost required to acquire all fruits from index i to the end.
- For each fruit i that you decide to purchase, you can choose a free block length k (0 ≤ k ≤ min(n – (i+1), i+1)) that you will take for free; then the next fruit to “handle” is at index i + 1 + k.
Space and Time Complexity
Time Complexity: O(n^2) in the worst case since for each fruit index i (n up to 1000) we try up to (i+1) possible free block lengths. Space Complexity: O(n) used by the dp array.
Solution
We solve the problem with dynamic programming by defining dp[i] as the minimum cost to acquire all fruits from index i to the end; our final answer will be dp[0]. Since fruit 0 cannot be obtained for free (there is no previous purchase with a reward covering it), we must purchase it. When purchasing fruit i for cost prices[i], we have the choice to use the reward associated with it to cover the next up to (i+1) fruits free – we can choose any k between 0 and min(n – i – 1, i+1) as the number of fruits to take for free. Thus, the recurrence is:
dp[i] = prices[i] + min{ dp[i + 1 + k] for all 0 ≤ k ≤ min(n – i – 1, i+1) }
The base case is dp[n] = 0 (when there are no fruits left to consider).
This recurrence correctly models the tradeoff: using a reward to get several fruits free versus buying some fruits (even if they could be free) to obtain a reward for an even larger free block later. We then build the dp array backwards from the end.