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 1-indexed array prices, where prices[i] denotes the number of coins needed to purchase the ith fruit.
The fruit market has the following offer:
- If you purchase the
ithfruit atprices[i]coins, you can get the nextifruits 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 1st fruit with 3 coins, you are allowed to take the 2nd fruit for free. - Purchase the 2nd fruit with 1 coin, you are allowed to take the 3rd fruit for free. - Take the 3rd fruit for free. Note that even though you were allowed to take the 2nd 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 1st fruit with 1 coin, you are allowed to take the 2nd fruit for free. - Take the 2nd fruit for free. - Purchase the 3rd fruit for 1 coin, you are allowed to take the 4th fruit for free. - Take the 4th 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 <= 10001 <= prices[i] <= 105
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[i-1] } 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[i-1]) } } 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); }