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]
    }
}