120. 三角形最小路径和

难度：中等

题目

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

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

自顶向下的最小路径和为11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用\(O(n)\)的额外空间（\(n\)为三角形的总行数）来解决这个问题，那么你的算法会很加分。

Reference

题解

基本思路： 动态规划，使用三角形的最后一行存放最小的和，从下往上进行计算。

代码如下：

#define MIN(x, y) (x < y ? x : y)
int minimumTotal(int **triangle, int triangleSize, int *triangleColSize)
{
    if (!triangleSize)
        return 0;
    int *dp1 = triangle[triangleSize - 1], i = 0, j = 0;
    for (i = triangleSize - 1; i > 0; i--)
        for (j = 0; j < triangleColSize[i - 1]; j++)
            dp1[j] = triangle[i - 1][j] + MIN(dp1[j], dp1[j + 1]);
    return dp1[0];
}

评论