package code;

import java.util.ArrayList;
import java.util.List;


public class Triangle {
	
 public int minimumTotal(List<List<Integer>> triangle) {
 	int n=triangle.size();
 	int[][] dp=new int[2][n];
 	if(n==0)	return 0;
 	if(n==1)	return triangle.get(0).get(0);
 	int ans=Integer.MAX_VALUE;
 	dp[0][0]=triangle.get(0).get(0);
 	int index=0;
 	for(int i=1;i<n;i++){
 		for(int j=0;j<=i;j++){
 			if(j==0){
 				dp[(index+1)%2][j]=dp[index%2][j];
 			}
 			else if(j==i){
 				dp[(index+1)%2][j]=dp[index%2][j-1];
 			}
 			else {
 				if(dp[index%2][j]>dp[index%2][j-1])
 					dp[(index+1)%2][j]=dp[index%2][j-1];
 				else dp[(index+1)%2][j]=dp[index%2][j];
 			}
 			dp[(index+1)%2][j]+=triangle.get(i).get(j);
 		}
 		index++;
 		for(int j=0;j<=i;j++)
 			System.out.println(dp[index%2][j]);
 		
 	}
 	for(int i=0;i<n;i++){
 		if(ans>dp[index%2][i])
 			ans=dp[index%2][i];
 	}
 return ans;
 }
	public static void main(String[] args){
		List<List<Integer>> triangle=new ArrayList<List<Integer>>();
		List<Integer> list1=new ArrayList<Integer>();
		list1.add(1);
		List<Integer> list2=new ArrayList<Integer>();
		list2.add(2);
		list2.add(3);
		triangle.add(list1);
		triangle.add(list2);
		Triangle tri=new Triangle();
		System.out.println(tri.minimumTotal(triangle));
	}
}