public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
		// Start typing your Java solution below
		// DO NOT write main() function
		int rows = triangle.size();
		if (rows == 0) {
			return 0;
		}

		int[] minSum = new int[rows];
		for (int i = 0; i < rows; i++) {
			int[] temp = new int[rows];
			ArrayList<Integer> level = triangle.get(i);
			if (level.size() != i + 1) {
				return -1;// input error
			}
			// first element
			temp[0] = level.get(0) + ((i > 0) ? minSum[0] : 0);
			// middle elements
			for (int j = 1; j < i; j++) {
				temp[j] = Math.min(minSum[j - 1], minSum[j]) + level.get(j);
			}
			// last element
			temp[i] = level.get(i) + ((i > 0) ? minSum[i - 1] : 0);

			minSum = temp;// update minSum
			// System.out.println("minSum "+minSum[0]+" "+minSum[1]+" "+minSum[2]);
		}

		// scan minSum and find the smallest value
		int min = Integer.MAX_VALUE;
		for (int k = 0; k < rows; k++) {
			min = Math.min(min, minSum[k]);
		}
		return min;

	}