Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        // write your code here
        if (triangle == null || triangle.size() == 0) return 0;

        int row = triangle.size();
        int[] sum = new int[triangle.get(row-1).size()];
        //from bottom to top
        for (int i = row - 1; i >= 0; i--) {
           int col = triangle.get(i).size();
           for (int j = 0; j < col; j++) {
               if (i == row - 1) {//last row, just copy elements
                   sum[j] = triangle.get(i).get(j);
               } else {
                   sum[j] = Math.min(sum[j], sum[j+1]) + triangle.get(i).get(j);
               }
           }
        }
        return sum[0];
    }
}

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """

        if not triangle:
            return -1

        dp = triangle[-1]
        for row in reversed(triangle[:-1]):
            for j, num in enumerate(row):
                dp[j] = min(dp[j], dp[j + 1]) + num
        return dp[0]