LeetCode 120. Triangle [Medium] [C++] 解題筆記

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

想法:

        宣告一個跟最後一列大小相等的 array，由上而下，由右至左遍歷，注意! 一定要由右至左，因為要找到當前位置可以累加出的最小和必須要知道上一列的 col j 與 col j-1 (假設當前位置為當前列的 col j)，因為我們只使用一個一維陣列來紀錄所以由左至右遍歷的話會把 col j - 1的資訊洗掉，因此一定要由右至左遍歷!

res[j] = ((j == 0)? res[j] : min(res[j], res[j - 1])) + triangle[i][j];

完整程式碼:

class Solution {

public:

    int minimumTotal(vector<vector<int>>& triangle) {

        vector<int> res(triangle.size(), INT_MAX);

        res[0] = triangle[0][0];

        for (int i = 1; i < triangle.size(); i++) {

            for (int j = i; j >= 0; j--) {

                res[j] = ((j == 0)? res[j] : min(res[j], res[j - 1])) + triangle[i][j];

            }

        }

        /*int min_sum = INT_MAX;

        for (int i = 0; i < res.size(); i++) {

            min_sum = min(min_sum, res[i]);

        }

        return min_sum;*/

        return *min_element(res.begin(), res.end());

    }

};