# 120. Triangle

[**120. Triangle**](https://leetcode.com/problems/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`

&#x20;**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.&#x20;

```
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];
    }
}
```
