# 120. Triangle

## 1.問題 

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意:  binary tree的類型, 若非perfect tree, 則無法確定left或right一定存在
* function header, parameter
* test input
* 觀察
  * 第一個邊有一個成員, 第二個邊有兩個成員, 第三個邊有三個成員, 這是一個正三角形
* 說明想法
  * 動態規劃, 跟機器人的路線可能性很像, 不同的只是改成了三角形, 左右兩邊  (正確來說是對角線與row 0)的規則是matrix\[j]\[i] += matrix\[j - 1]\[i], 而中心部分的來源有兩個, 取最小值
  * 切記matrix的縱座標為row (y), 橫坐標為column(x), 表示法為matrix\[r]\[c]&#x20;
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.size() == 0) {
            return 0;
        }
        
        int n = triangle.size();
        for (int r = 1; r < n; r++) {
            //對角線
            triangle[r][0] += triangle[r - 1][0]; 
            triangle[r][r] += triangle[r - 1][r - 1];
            
            //中間
            for (int c = 1; c < triangle[r].size() - 1; c++) {
                triangle[r][c] = triangle[r][c] + min(triangle[r - 1][c - 1], triangle[r - 1][c]);
            }
        }
        
        int minVal = INT_MAX;
        
        for (int c = 0; c < triangle[n - 1].size(); c++) {
            minVal = min(minVal, triangle[n - 1][c]);
        }
        
        return minVal;
    }
};
```