Leetcode 120. Triangle in C [C語言]
==
###### tags: `Leetcode` `DP`

## Description
(medium)
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

## 思路
一開始還沒什麼想法先用greedy寫一個top-down的方法，但是寫一寫大概就知道很容易出錯，所以就理所當然的出錯了，尤其是當裡面有負數的時候。

這時候想到應該使用bottom-up的DP才對，從右下角開始對每一個小三角形取最佳解，然後往上推一層，重複這動作直到最後。

2 2 2 11
3 4 -> 3 4 -> 9 10 ->
6 5 7 7 6 10
4 1 8 3
這樣很快就可以得到答案

timcomplexity 大約是在O(n)

## 程式

#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))

int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){
    if(triangleSize==1) return triangle[0][0];
    for(int i=triangleSize-2; i>=0; i--){
        for(int j=triangleColSize[i]-1; j>=0; j--){
            triangle[i][j]+=MIN(triangle[i+1][j],triangle[i+1][j+1]);
        }
    }
    return triangle[0][0];
}