Welcome to Subscribe On Youtube
2944. Minimum Number of Coins for Fruits
Description
You are at a fruit market with different types of exotic fruits on display.
You are given a 1indexed array prices
, where prices[i]
denotes the number of coins needed to purchase the i^{th}
fruit.
The fruit market has the following offer:
 If you purchase the
i^{th}
fruit atprices[i]
coins, you can get the nexti
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 a new offer.
Return the minimum number of coins needed to acquire all the fruits.
Example 1:
Input: prices = [3,1,2] Output: 4 Explanation: You can acquire the fruits as follows:  Purchase the 1^{st} fruit with 3 coins, you are allowed to take the 2^{nd} fruit for free.  Purchase the 2^{nd} fruit with 1 coin, you are allowed to take the 3^{rd} fruit for free.  Take the 3^{rd} fruit for free. Note that even though you were allowed to take the 2^{nd} fruit for free, you purchased it because it is more optimal. It can be proven that 4 is the minimum number of coins needed to acquire all the fruits.
Example 2:
Input: prices = [1,10,1,1] Output: 2 Explanation: You can acquire the fruits as follows:  Purchase the 1^{st} fruit with 1 coin, you are allowed to take the 2^{nd} fruit for free.  Take the 2^{nd} fruit for free.  Purchase the 3^{rd} fruit for 1 coin, you are allowed to take the 4^{th} fruit for free.  Take the 4^{t}^{h} fruit for free. It can be proven that 2 is the minimum number of coins needed to acquire all the fruits.
Constraints:
1 <= prices.length <= 1000
1 <= prices[i] <= 10^{5}
Solutions
Method 1: Memoization Search
We define a function $dfs(i)$, which represents the minimum number of coins needed to buy all fruits starting from the $i$th fruit. So the answer is $dfs(1)$.
The execution logic of the function $dfs(i)$ is as follows:
 If $i \times 2 \geq n$, it means that we only need to buy the $i  1$th fruit, and the remaining fruits can be obtained for free, so return $prices[i  1]$.
 Otherwise, we can buy fruit $i$, and then choose a fruit $j$ to start buying from the next $i + 1$ to $2i + 1$ fruits, so $dfs(i) = prices[i  1] + \min_{i + 1 \le j \le 2i + 1} dfs(j)$.
To avoid repeated calculations, we use the method of memoization search, save the calculated results, and directly return the result when encountering the same situation next time.
The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Where $n$ is the length of the array $prices$.
Method 2: Dynamic Programming
We can rewrite the memoization search in Method 1 into the form of dynamic programming.
Similar to Method 1, we define $f[i]$ as the minimum number of coins needed to buy all fruits starting from the $i$th fruit. So the answer is $f[1]$.
The state transition equation is $f[i] = \min_{i + 1 \le j \le 2i + 1} f[j] + prices[i  1]$.
In implementation, we calculate from back to front, and we can directly perform state transition on the array $prices$, which can save space.
The time complexity is $O(n^2)$, where $n$ is the length of the array $prices$. The space complexity is $O(1)$.
Method 3: Dynamic Programming + Monotonic Queue Optimization
We observe the state transition equation in Method 2, and find that for each $i$, we need to find the minimum value of $f[i + 1], f[i + 2], \cdots, f[2i + 1]$, and as $i$ decreases, the range of these values is also decreasing. This is actually finding the minimum value of a monotonically narrowing sliding window, and we can use a monotonic queue to optimize.
We calculate from back to front, maintain a monotonically increasing queue $q$, and the queue stores the index. If the head element of $q$ is greater than $i \times 2 + 1$, it means that the elements after $i$ will not be used, so we dequeue the head element. If $i$ is not greater than $(n  1) / 2$, then we can add $prices[q[0]  1]$ to $prices[i  1]$, and then add $i$ to the tail of the queue. If the price of the fruit corresponding to the tail element of $q$ is greater than or equal to $prices[i  1]$, then we dequeue the tail element until the price of the fruit corresponding to the tail element is less than $prices[i  1]$ or the queue is empty, and then add $i$ to the tail of the queue.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array $prices$.

class Solution { private int[] prices; private int[] f; private int n; public int minimumCoins(int[] prices) { n = prices.length; f = new int[n + 1]; this.prices = prices; return dfs(1); } private int dfs(int i) { if (i * 2 >= n) { return prices[i  1]; } if (f[i] == 0) { f[i] = 1 << 30; for (int j = i + 1; j <= i * 2 + 1; ++j) { f[i] = Math.min(f[i], prices[i  1] + dfs(j)); } } return f[i]; } }

class Solution { public: int minimumCoins(vector<int>& prices) { int n = prices.size(); int f[n + 1]; memset(f, 0x3f, sizeof(f)); function<int(int)> dfs = [&](int i) { if (i * 2 >= n) { return prices[i  1]; } if (f[i] == 0x3f3f3f3f) { for (int j = i + 1; j <= i * 2 + 1; ++j) { f[i] = min(f[i], prices[i  1] + dfs(j)); } } return f[i]; }; return dfs(1); } };

class Solution: def minimumCoins(self, prices: List[int]) > int: @cache def dfs(i: int) > int: if i * 2 >= len(prices): return prices[i  1] return prices[i  1] + min(dfs(j) for j in range(i + 1, i * 2 + 2)) return dfs(1)

func minimumCoins(prices []int) int { n := len(prices) f := make([]int, n+1) var dfs func(int) int dfs = func(i int) int { if i*2 >= n { return prices[i1] } if f[i] == 0 { f[i] = 1 << 30 for j := i + 1; j <= i*2+1; j++ { f[i] = min(f[i], dfs(j)+prices[i1]) } } return f[i] } return dfs(1) }

function minimumCoins(prices: number[]): number { const n = prices.length; const f: number[] = Array(n + 1).fill(0); const dfs = (i: number): number => { if (i * 2 >= n) { return prices[i  1]; } if (f[i] === 0) { f[i] = 1 << 30; for (let j = i + 1; j <= i * 2 + 1; ++j) { f[i] = Math.min(f[i], prices[i  1] + dfs(j)); } } return f[i]; }; return dfs(1); }