# LeetCode - 0120. Triangle
### 題目網址：https://leetcode.com/problems/triangle/
###### tags: `LeetCode` `Medium` `動態規劃（Dynamic Programming）`

/*
    -LeetCode format-
    Problem: 120. Triangle
    Difficulty: Medium
    
    by Inversionpeter
*/



static const auto Initialize = []{
    ios::sync_with_stdio(false); cout.tie(nullptr);
    return nullptr;
}();

int DP[2][200];

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int rows = triangle.size(), columns, minimum = 2147483647;
        DP[0][0] = triangle[0][0];
        for (int i = 1; i < rows; ++i) {
            columns = triangle[i].size();
            DP[i & 1][0] = DP[!(i & 1)][0] + triangle[i][0];
            for (int j = 1; j < columns - 1; ++j)
                DP[i & 1][j] = min(DP[!(i & 1)][j - 1], DP[!(i & 1)][j]) + triangle[i][j];
            DP[i & 1][columns - 1] = DP[!(i & 1)][columns - 2] + triangle[i][columns - 1];
        }
        for (int i = (rows - 1) & 1, j = 0; j != triangle.back().size(); ++j)
            minimum = min(minimum, DP[i][j]);
        return minimum;
    }
};