import java.util.Arrays;

import java.util.List;

import com.sun.management.jmx.Trace;

public class minimumTotal {

int minSum=Integer.MAX_VALUE;

public int mintotal(List<List<Integer>> triangle) {

int minSum;

if(triangle.size()==0|| triangle.get(0).size()==0) {

return 0;

}

return _dfs(triangle, 0, 0,"",0);

}

private int _dfs(List<List<Integer>> triangle,int i,int j,String path,int sum) {

if(i==triangle.size()-1) {

path+=triangle.get(i).get(j);

sum+=triangle.get(i).get(j);

minSum=Math.min(sum, minSum);

System.out.println(path+" with sum: "+ sum);

System.out.println(minSum);

return 0;

}

path+=triangle.get(i).get(j)+"->";

sum+=triangle.get(i).get(j);

_dfs(triangle, i+1, j,path,sum);

_dfs(triangle, i+1, j+1,path,sum);

return 0;

}

public int mintotal2(List<List<Integer>> triangle) {

int minSum;

if(triangle.size()==0|| triangle.get(0).size()==0) {

return 0;

}

for(int i=triangle.size()-2;i>=0;--i) {

for(int j=triangle.get(i).size()-1;j>=0;--j) {

int min=Math.min(triangle.get(i+1).get(j), triangle.get(i+1).get(j+1));

min+=triangle.get(i).get(j);

triangle.get(i).set(j, min);

}

}

return triangle.get(0).get(0);

}

public static void main(String[] args) {

// TODO Auto-generated method stub

minimumTotal oneMinimumTotal=new minimumTotal();

int result=oneMinimumTotal.mintotal(Arrays.asList(

Arrays.asList(2),

Arrays.asList(3,4),

Arrays.asList(6,5,7),

Arrays.asList(4,1,8,3)

));

System.out.println(11);

}

}