120.Triangle

Tags: Medium Dynamic Programming

Links: https://leetcode.com/problems/triangle/

---

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.

---

数字三角形的模板题，注意follow up里面的空间优化选项，因为状态转移方程之和d[i - 1]相关，所以完全可以只用一个一维数组，空间复杂度$O(n)$。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = triangle.size();
        vector<int> d(n);
        d[0] = triangle[0][0];

        for (int i = 1; i < n; ++i) {
            for (int j = i; j >= 0; --j) {
                if (j == 0) d[j] += triangle[i][j];
                else if (j == i) d[j] = d[j - 1] + triangle[i][j];
                else d[j] = min(d[j], d[j - 1]) + triangle[i][j];
            }
        }

        return *min_element(d.begin(), d.end());
    }
};