2944. Minimum Number of Coins for Fruits Medium

1/**
2 * [2944] Minimum Number of Coins for Fruits
3 *
4 * You are given an 0-indexed integer array prices where prices[i] denotes the number of coins needed to purchase the (i + 1)^th fruit.
5 * The fruit market has the following reward for each fruit:
6 * 
7 * 	If you purchase the (i + 1)^th fruit at prices[i] coins, you can get any number of the next i fruits for free.
8 * 
9 * Note that even if you can take fruit j for free, you can still purchase it for prices[j - 1] coins to receive its reward.
10 * Return the minimum number of coins needed to acquire all the fruits.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">prices = [3,1,2]</span>
15 * Output: <span class="example-io">4</span>
16 * Explanation:
17 * 
18 * 	Purchase the 1^st fruit with prices[0] = 3 coins, you are allowed to take the 2^nd fruit for free.
19 * 	Purchase the 2^nd fruit with prices[1] = 1 coin, you are allowed to take the 3^rd fruit for free.
20 * 	Take the 3^rd fruit for free.
21 * 
22 * Note that even though you could take the 2^nd fruit for free as a reward of buying 1^st fruit, you purchase it to receive its reward, which is more optimal.
23 * </div>
24 * <strong class="example">Example 2:
25 * <div class="example-block">
26 * Input: <span class="example-io">prices = [1,10,1,1]</span>
27 * Output: <span class="example-io">2</span>
28 * Explanation:
29 * 
30 * 	Purchase the 1^st fruit with prices[0] = 1 coin, you are allowed to take the 2^nd fruit for free.
31 * 	Take the 2^nd fruit for free.
32 * 	Purchase the 3^rd fruit for prices[2] = 1 coin, you are allowed to take the 4^th fruit for free.
33 * 	Take the 4^t^h fruit for free.
34 * </div>
35 * <strong class="example">Example 3:
36 * <div class="example-block">
37 * Input: <span class="example-io">prices = [26,18,6,12,49,7,45,45]</span>
38 * Output: <span class="example-io">39</span>
39 * Explanation:
40 * 
41 * 	Purchase the 1^st fruit with prices[0] = 26 coin, you are allowed to take the 2^nd fruit for free.
42 * 	Take the 2^nd fruit for free.
43 * 	Purchase the 3^rd fruit for prices[2] = 6 coin, you are allowed to take the 4^th, 5^th and 6^th (the next three) fruits for free.
44 * 	Take the 4^t^h fruit for free.
45 * 	Take the 5^t^h fruit for free.
46 * 	Purchase the 6^th fruit with prices[5] = 7 coin, you are allowed to take the 8^th and 9^th fruit for free.
47 * 	Take the 7^t^h fruit for free.
48 * 	Take the 8^t^h fruit for free.
49 * 
50 * Note that even though you could take the 6^th fruit for free as a reward of buying 3^rd fruit, you purchase it to receive its reward, which is more optimal.
51 * </div>
52 *  
53 * Constraints:
54 * 
55 * 	1 <= prices.length <= 1000
56 * 	1 <= prices[i] <= 10^5
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/minimum-number-of-coins-for-fruits/
62// discuss: https://leetcode.com/problems/minimum-number-of-coins-for-fruits/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn minimum_coins(prices: Vec<i32>) -> i32 {
68        0
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_2944() {
80    }
81}
82