1000. Minimum Cost to Merge Stones Hard

1/**
2 * [1000] Minimum Cost to Merge Stones
3 *
4 * There are n piles of stones arranged in a row. The i^th pile has stones[i] stones.
5 * A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles.
6 * Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.
7 *  
8 * Example 1:
9 * 
10 * Input: stones = [3,2,4,1], k = 2
11 * Output: 20
12 * Explanation: We start with [3, 2, 4, 1].
13 * We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
14 * We merge [4, 1] for a cost of 5, and we are left with [5, 5].
15 * We merge [5, 5] for a cost of 10, and we are left with [10].
16 * The total cost was 20, and this is the minimum possible.
17 * 
18 * Example 2:
19 * 
20 * Input: stones = [3,2,4,1], k = 3
21 * Output: -1
22 * Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.
23 * 
24 * Example 3:
25 * 
26 * Input: stones = [3,5,1,2,6], k = 3
27 * Output: 25
28 * Explanation: We start with [3, 5, 1, 2, 6].
29 * We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
30 * We merge [3, 8, 6] for a cost of 17, and we are left with [17].
31 * The total cost was 25, and this is the minimum possible.
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	n == stones.length
37 * 	1 <= n <= 30
38 * 	1 <= stones[i] <= 100
39 * 	2 <= k <= 30
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/minimum-cost-to-merge-stones/
45// discuss: https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn merge_stones(stones: Vec<i32>, k: i32) -> i32 {
51        0
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_1000() {
63    }
64}
65