120. Triangle Medium

1/**
2 * [120] Triangle
3 *
4 * Given a triangle array, return the minimum path sum from top to bottom.
5 * For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
6 *  
7 * Example 1:
8 * 
9 * Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
10 * Output: 11
11 * Explanation: The triangle looks like:
12 *    <u>2</u>
13 *   <u>3</u> 4
14 *  6 <u>5</u> 7
15 * 4 <u>1</u> 8 3
16 * The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
17 * 
18 * Example 2:
19 * 
20 * Input: triangle = [[-10]]
21 * Output: -10
22 * 
23 *  
24 * Constraints:
25 * 
26 * 	1 <= triangle.length <= 200
27 * 	triangle[0].length == 1
28 * 	triangle[i].length == triangle[i - 1].length + 1
29 * 	-10^4 <= triangle[i][j] <= 10^4
30 * 
31 *  
32 * Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/triangle/
37// discuss: https://leetcode.com/problems/triangle/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
43        0
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_120() {
55    }
56}
57