120. Triangle

120. Triangle

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

• 1 <= triangle.length <= 200

• triangle[0].length == 1

• triangle[i].length == triangle[i - 1].length + 1

• -104 <= triangle[i][j] <= 104

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

My Solutions:

从下往上遍历triangle的每一层，因为最底层element的数量和triangle的row数是相同的，所以只需要用一个int[] dp = int[rows] 来储存最优解。

对于每一个element，可以到达这个elment的方式只有两种：1。从下一层的同一index位置的element上来；2。从下一层的index+1位置的element上来。在这两种方式中，dp 记录最小值。对于最下面一行的element，只需要把dp[j]设置成 triangle.get(i).get(j)，不需要加上到达这个element的路径，不然会有index out of bound error.

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;
        
        int rows = triangle.size();
        int[] dp = new int[rows];
        
        //bottom up
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                if (i == rows - 1) dp[j] = triangle.get(i).get(j);
                else dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
}