## 120. Triangle

Given a `triangle` array, return the minimum path sum from top to bottom.

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.

Example 1:

```Input: triangle = [,[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
```

Example 2:

```Input: triangle = [[-10]]
Output: -10
```

Constraints:

• `1 <= triangle.length <= 200`
• `triangle.length == 1`
• `triangle[i].length == triangle[i - 1].length + 1`
• `-104 <= triangle[i][j] <= 104`

Follow up: Could you do this using only `O(n)` extra space, where `n` is the total number of rows in the triangle?

## Rust Solution

``````struct Solution;

impl Solution {
fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
let n = triangle.len();
let mut dp = vec![vec![0; n + 1]; 2];
for i in (0..n).rev() {
for j in 0..=i {
dp[i % 2][j] = triangle[i][j] + dp[(i + 1) % 2][j].min(dp[(i + 1) % 2][j + 1]);
}
}
dp
}
}

#[test]
fn test() {
let triangle = vec_vec_i32![, [3, 4], [6, 5, 7], [4, 1, 8, 3]];
let res = 11;
assert_eq!(Solution::minimum_total(triangle), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.