class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 0)
            return 0;

        int[] dp = new int[triangle.size()];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = triangle.get(0).get(0);

        int minDst = triangle.get(0).get(0);
        for(int i = 1; i < triangle.size(); i++) {
            int curMinDst = Integer.MAX_VALUE;
            for (int j = triangle.get(i).size() - 1; j >= 0 ; j--) {
                int straightStep = dp[j];
                int sideStep = Integer.MAX_VALUE;
                int curItm = triangle.get(i).get(j);
                if(j > 0)
                    sideStep = dp[j - 1];

                int min = Math.min(straightStep, sideStep);
                dp[j] = min + curItm;
                curMinDst = Math.min(curMinDst, dp[j]);

            }
            minDst = curMinDst;
        }

        return minDst;
    }
}