1547. Minimum Cost to Cut a Stick Hard

1/**
2 * [1547] Minimum Cost to Cut a Stick
3 *
4 * Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:
5 * <img alt="" src="https://assets.leetcode.com/uploads/2020/07/21/statement.jpg" style="width: 521px; height: 111px;" />
6 * Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.
7 * You should perform the cuts in order, you can change the order of the cuts as you wish.
8 * The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.
9 * Return the minimum total cost of the cuts.
10 *  
11 * Example 1:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2020/07/23/e1.jpg" style="width: 350px; height: 284px;" />
13 * Input: n = 7, cuts = [1,3,4,5]
14 * Output: 16
15 * Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2020/07/21/e11.jpg" style="width: 350px; height: 284px;" />
17 * The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
18 * Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
19 * Example 2:
20 *
21 * Input: n = 9, cuts = [5,6,1,4,2]
22 * Output: 22
23 * Explanation: If you try the given cuts ordering the cost will be 25.
24 * There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.
25 *
26 *  
27 * Constraints:
28 *
29 * 2 <= n <= 10^6
30 * 1 <= cuts.length <= min(n - 1, 100)
31 * 1 <= cuts[i] <= n - 1
32 * All the integers in cuts array are distinct.
33 *
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/minimum-cost-to-cut-a-stick/
38// discuss: https://leetcode.com/problems/minimum-cost-to-cut-a-stick/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41use std::cmp;
42impl Solution {
43    pub fn min_cost(n: i32, cuts: Vec<i32>) -> i32 {
44        let mut data = cuts.clone();
45        data.sort();
46        data.insert(0, 0);
47        data.push(n);
48        let mut dp = vec![vec![0; data.len()]; data.len()];
49
50        for i in (1..cuts.len() + 1).rev() {
51            for j in i..cuts.len() + 1 {
52                let cost = data[j + 1] - data[i - 1];
53                let mut min = i32::MAX;
54
55                for k in i..j + 1 {
56                    min = cmp::min(min, cost + dp[i][k - 1] + dp[k + 1][j]);
57                }
58
59                dp[i][j] = min;
60            }
61        }
62
63        dp[1][cuts.len()]
64    }
65
66    pub fn min_cost_recursive(n: i32, cuts: Vec<i32>) -> i32 {
67        let mut data = cuts.clone();
68        data.sort();
69        data.insert(0, 0);
70        data.push(n);
71        let mut dp = vec![vec![-1; data.len()]; data.len()];
72        Self::check(&mut dp, &data, 1, data.len() - 2)
73    }
74
75    fn check(dp: &mut Vec<Vec<i32>>, cuts: &Vec<i32>, s: usize, e: usize) -> i32 {
76        if s > e {
77            return 0;
78        }
79
80        if dp[s][e] != -1 {
81            return dp[s][e];
82        }
83
84        let mut local_min = i32::MAX;
85        for i in s..e + 1 {
86            let cost = cuts[e + 1] - cuts[s - 1]
87                + if dp[s][i - 1] != -1 {
88                    dp[s][i - 1]
89                } else {
90                    Self::check(dp, cuts, s, i - 1)
91                }
92                + if dp[i + 1][e] != -1 {
93                    dp[i + 1][e]
94                } else {
95                    Self::check(dp, cuts, i + 1, e)
96                };
97            local_min = cmp::min(local_min, cost);
98        }
99
100        dp[s][e] = local_min;
101        local_min
102    }
103}
104
105// submission codes end
106
107#[cfg(test)]
108mod tests {
109    use super::*;
110
111    #[test]
112    fn test_1547() {
113        assert_eq!(Solution::min_cost(9, vec![5, 6, 1, 4, 2]), 22);
114        assert_eq!(Solution::min_cost(7, vec![1, 3, 4, 5]), 16);
115    }
116
117    #[test]
118    fn test_1547_1() {
119        assert_eq!(
120            Solution::min_cost(
121                8753,
122                vec![
123                    6342, 6234, 1701, 5673, 944, 1019, 767, 6988, 4968, 6289, 8152, 8602, 2342,
124                    7532, 1555, 1551, 1817, 4286, 3335, 4424, 5346, 830, 1705
125                ]
126            ),
127            36873
128        );
129    }
130
131    #[test]
132    fn test_1547_2() {
133        assert_eq!(
134            Solution::min_cost(
135                10000,
136                vec![6816, 8372, 3750, 3661, 9442, 4813, 1507, 1421, 5448, 7405, 2401]
137            ),
138            35316
139        );
140    }
141}
142