120. Triangle

Leetcode Array Dynamic Programming

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.

分析

动态规划，关键是寻找最小路径和之间的关系：

public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle == null) return 0;
    int m = triangle.size();
    int [][] pathSum = new int[m][m];  
    // initialize
    for (int j = 0; j < m; j++)
        pathSum[m - 1][j] = triangle.get(m - 1).get(j);

    for (int i = m - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            pathSum[i][j] = triangle.get(i).get(j) +
                     Math.min(pathSum[i + 1][j], pathSum[i + 1][j + 1]);

    return pathSum[0][0];
}

题目还提到了能不能把算法优化到$O(n)$的空间复杂度。观察

pathSum[i][j] = triangle.get(i).get(j) + Math.min(pathSum[i + 1][j], pathSum[i + 1][j + 1]);

等式左边总是第i行，右边总是i+1行，所以更新不重叠，只需要一个一维数组就行了。

public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle == null) return 0;
    int m = triangle.size();
    int [] pathSum = new int[m];  
    // initialize
    for (int j = 0; j < m; j++)
        pathSum[j] = triangle.get(m - 1).get(j);

    for (int i = m - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            pathSum[j] = triangle.get(i).get(j) + Math.min(pathSum[j], pathSum[j + 1]);


    return pathSum[0];
}