solve #120

aylei · aylei · commit a0b723061d6e · 2019-02-16T21:51:36.000+08:00
diff --git a/src/lib.rs b/src/lib.rs
@@ -118,3 +118,4 @@ mod n0114_flatten_binary_tree_to_linked_list;
 mod n0115_distinct_subsequences;
 mod n0118_pascals_triangle;
 mod n0119_pascals_triangle_ii;
+mod n0120_triangle;
diff --git a/src/n0120_triangle.rs b/src/n0120_triangle.rs
@@ -0,0 +1,69 @@
+/**
+ * [120] Triangle
+ *
+ * Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
+ * 
+ * For example, given the following triangle
+ * 
+ * 
+ * [
+ *      [2],
+ *     [3,4],
+ *    [6,5,7],
+ *   [4,1,8,3]
+ * ]
+ *
+ * 
+ * The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
+ * 
+ * Note:
+ * 
+ * Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
+ * 
+ */
+pub struct Solution {}
+
+// submission codes start here
+
+impl Solution {
+    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
+        let mut cache = vec![0; triangle.len()];
+        for row in triangle.iter() {
+            let mut prev = 0;
+            for i in 0..row.len() {
+                let temp = cache[i];
+                cache[i] = if i == 0 {
+                    cache[i]
+                } else if i == row.len() - 1 {
+                    prev
+                } else {
+                    i32::min(cache[i], prev)
+                } + row[i];
+                prev = temp;
+            }
+        }
+        cache.into_iter().fold(i32::max_value(), |min, x| i32::min(min, x))
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_120() {
+        assert_eq!(
+            Solution::minimum_total(
+                vec![
+                    vec![2],
+                    vec![3,4],
+                    vec![6,5,7],
+                    vec![4,1,8,3]
+                ]
+            ),
+            11
+        )
+    }
+}
