LeetCode 120 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.

Diffculty Medium

Similar Problems [LeetCode 118] Pascal's Triangle E [LeetCode 119] Pascal's Triangle II E

Analysis

这道题就是一道典型的动态规划的模板题。用 minPath[i][j]表示以第 i 层第 j 个节点为终点的最小路径，因为第 i 层第 j 个节点只能从第 i - 1 层的第 j 个和第 j - 1 节点达到，那么状态转移方程为

minPath[i][j] = min(minPath[i−1][j−1], minPath[i−1][j]) + triangle[i][j]

因为题目要求是O（n）的空间复杂度，而从状态转移方程可以看出求第 i 层的路径时只用到了第 i - 1 层，这层以前的数据都不再需要，因此，可以只申请一个大小为 n 的 vector，保存某一层的结果，由于计算时需要用到 j 以及 j - 1 ，因此需要从最后一个元素开始更新 vector 的值，状态转移方程就变成了

minPath[j] = min(minPath[j−1], minPath[j]) + triangle[i][j]

由于 vector 初始化为 0，所以对于右边界的情况可以不用考虑，而对于左边界的情况，

minPath[0] = minPath[0] + triangle[i][0]

最后找到了到第 N 层各元素的最小路径，通过一次遍历得到最小的路径值。整个过程可以对照着下面的实现结合画图理解。

参考思路：

惯例通过之后看了一下其他人的答案，其他人的解法是自底向上，上一层元素最小路径是由该元素的两个孩子元素求得，状态转移方程为

minpath[i] = min(minpath[i], minpath[i+1]) + triangle[k][i]

最后返回 minPath[0] 即可。

思路： 这题用到了一点DP的思路，即存储每一层的结果，来计算下一层。关键点在于要用 O(n) 空间。 用两个数组prePath和curPath分别存储上一层和本层的每个坐标的 min path sum。如果已知 prePath，则可以计算 curPath：

1. 对第j层 (j = 0 ~ n-1)，一共有j+1个数：0:j。而上一层有j个数：0:j-1
2. 除去头尾两个数外，curPath[i] = min(prePath[i-1], prePath[i]) + triangle[j][i]
3. 头尾的特殊情况：curPath[0] = prePath[0] + triangle[j][0]；curPath[j] = prePath[j-1] + triangle[j][j]
4. 在计算下一层前，需要交换curPath和prePath。
5. 在最后一层curPath计算结束后，在其中找一个最小值即为整个树的min path sum。

额外存储空间是2n。尽管通过滚动数组也可以事先n，但代码要复杂很多，面试短时间内容易出错。

Analysis: DP problem, Transaction function: A[n][i] = A[n][i] + min(a[n-1][i], a[n-1][i-1]). Note that in this problem, "adjacent" of a[i][j] means a[i-1][j] and a[i-1][j-1], if available(not out of bound), while a[i-1][j+1] is not "adjacent" element. If we do this from up to down, it is complicated. While from down to up, we could use only one array to scan every row to get result

Solutions

1. 自底向上

int minimumTotal(vector<vector<int> > &triangle) {
    int row = triangle.size();
    if(row == 0) return 0;

    vector<int> minV(triangle[row - 1].size()); // dp[] 记录每一层，每一个元素所能达到的路径的最小值
    for(int i = row - 1; i >= 0; i--) {
        for(int j = 0; j < (int)triangle[i].size(); j++) {
            if(i == row - 1) { // 初始值，因为是从最低层开始遍历，因此把 dp[] 初始值赋值为当前层的元素值
                minV[j] = triangle[i][j];
                continue;
            }
            minV[j] = min(minV[j], minV[j + 1]) + triangle[i][j];
        }
    }
    return minV[0];
}

也可以直接用 vector<int> minPath(triangle.back()); 来初始化

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> minPath(triangle.back());

        for (int layer = n - 2; layer >= 0; layer--) {
            for (int i = 0; i <= layer; i++) {
                minPath[i] = min(minPath[i], minPath[i + 1]) + triangle[layer][i];
            }
        }

        return minPath[0];
    }
};

1. 自顶向下

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty()) return 0;
        int n = triangle.size();
        vector<int> curPath(n,INT_MAX);
        vector<int> prePath(n,INT_MAX);
        curPath[0] = triangle[0][0];

        for(int j = 1; j<n; j++) {
            prePath = curPath;
            curPath[0] = prePath[0] + triangle[j][0];
            curPath[j] = prePath[j-1] + triangle[j][j];
            for(int i = 1; i < j; i++)
                curPath[i] = min(prePath[i-1], prePath[i]) + triangle[j][i];
        }

        int minPath = INT_MAX;
        for(int i=0; i<n; i++)
            minPath = min(minPath, curPath[i]);

        return minPath;
    }
};

Reference