package com.fishercoder.solutions;

import java.util.List;

/**
 * 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.*/

public class _120 {
  public static class Solution1 {
    public int minimumTotal(List<List<Integer>> triangle) {
      int n = triangle.size();
      List<Integer> cache = triangle.get(n - 1);

      for (int layer = n - 2; layer >= 0; layer--) {
        //for each layer
        for (int i = 0; i <= layer; i++) {
          //check its very node
          int value = Math.min(cache.get(i), cache.get(i + 1)) + triangle.get(layer).get(i);
          cache.set(i, value);
        }
      }
      return cache.get(0);
    }
  }
}

@@ -57,450 +57,8 @@
 t;%0A%0A
-/**%0A * 120. Triangle%0A%0A  Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.%0A%0A For example, given the following triangle%0A %5B%0A %5B2%5D,%0A %5B3,4%5D,%0A %5B6,5,7%5D,%0A %5B4,1,8,3%5D%0A %5D%0A The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).%0A%0A Note:%0A 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.*/%0A%0A
 publ
@@ -73,16 +73,18 @@
  _120 %7B%0A
+  
   public
@@ -109,24 +109,28 @@
 tion1 %7B%0A    
+   
+ 
 public int m
@@ -169,24 +169,30 @@
 triangle) %7B%0A
+      
       int n 
@@ -216,16 +216,22 @@
 ;%0A      
+ 
+     
 List%3CInt
@@ -268,24 +268,30 @@
  1);%0A%0A      
+   
+   
 for (int lay
@@ -333,16 +333,24 @@
         
+     
+   
 //for ea
@@ -358,16 +358,24 @@
 h layer%0A
+        
         
@@ -419,16 +419,26 @@
         
+      
+    
 //check 
@@ -451,16 +451,26 @@
 ry node%0A
+          
         
@@ -564,16 +564,26 @@
         
+   
+       
 cache.se
@@ -603,24 +603,46 @@
         
+        %7D%0A            
 %7D%0A      
 %7D%0A      
@@ -629,26 +629,24 @@
     %7D%0A      
-%7D%0A
       return
@@ -664,16 +664,22 @@
 0);%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 120