[−][src]Function leetcode_for_rust::cd0120_triangle::minimum_total
pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32
Solutions
Approach 1: Dynamic Programming
-
Time complexity: O(n)
-
Space complexity: O(n)
-
Runtime: 0 ms
-
Memory: 2.6 MB
impl Solution { pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 { if triangle.len() == 0 { return 0; } let mut min = triangle.last().unwrap().clone(); for i in (0..triangle.len() - 1).rev() { for j in 0..triangle[i].len() { min[j] = min[j].min(min[j + 1]) + triangle[i][j]; } } min[0] } }
Approach 2: Dynamic Programming
-
Time complexity: O(n)
-
Space complexity: O(1)
-
Runtime: 0 ms
-
Memory: 2.7 MB
impl Solution { pub fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 { if triangle.len() == 0 { return 0; } for i in (0..triangle.len() - 1).rev() { for j in 0..triangle[i].len() { triangle[i][j] = triangle[i + 1][j].min(triangle[i + 1][j + 1]) + triangle[i][j]; } } triangle[0][0] } }