###### tags: `Leetcode` `medium` `dynamic programming` `python`

# 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.

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

**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

## 解題想法:
* 題目為，給定一個三角形數組，返回從上到下的最小路徑和
* 對於當前位置i
* 可以選擇移動到下一層的位置(i)或位置(i+1)

* 逆向思考:
* 從**bottomt to top**: dp[0][0]=final ans
* 從倒數第二層往回推算
* 對於當前的dp[i][j]
* 選擇下一層(i+1)的位置(j or j+1)小的進行累積
* dp[i][j]+=min(dp[i+1][j],dp[i+1][j+1])

說明:
            2                    ^
        3       4                |
    6       5       7       <--從此列開始往回推
4       1       8       3

更新6的位置 6可以由下層4 or 1到達 =>>  6+=min(4,1)  =>> 7
依序更新至triangle[0][0]即為答案

## Python: