120 Triangle

雖然他放在medium, 但這題真的蠻簡單的

這題目算是dp設計的基本題,

我們去設計所會發生的case

tri[i][j]:
 j = 0: 
       tri[i-1][0]
因為最邊邊只有一個上層可以參考, 所以沒得選
 j = tri[i].size() - 1
最後一個也在邊邊, 也只有一個上層可以選,
       tri[i-1][j-1]
else:
    tri[i][j] = tri[i][j] + min(tri[i-1][j-1], tri[i-1][j])

做完後從最後一列直接找最小值即可

code:

class Solution {
  public:
    int minimumTotal(vector<vector<int>> &triangle) {
        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 0; j < triangle[i].size(); j++) {
                if (j == 0) {
                    triangle[i][j] += triangle[i - 1][j];
                } else if (j == triangle[i].size() - 1) {
                    triangle[i][j] += triangle[i - 1][j - 1];
                } else {
                    triangle[i][j] =
                        triangle[i][j] +
                        min(triangle[i - 1][j - 1], triangle[i - 1][j]);
                }
            }
        }
        vector<int> final_v = triangle[triangle.size() - 1];
        int res = INT_MAX;
        for (auto &i : final_v) {
            res = min(res, i);
        }
        return res;
    }
};