LeetCode 120.Triangle (三角形最小路径和)-白红宇

LeetCode 120.Triangle (三角形最小路径和)

阅读量：2179 次

发布时间：2019-05-01

本文共 1065 字，大约阅读时间需要 3 分钟。

题目描述：

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

例如，给定三角形：

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

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

说明：

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

AC C++ Solution:

DP算法：一维数组动态记录,迭代更新自身

“自下而上”DP非常简单：我们从底行的节点开始; 这些节点的最小路径是节点本身的值。从那里开始，第k行第i个节点的最小路径将是其两个子节点的路径中的较小者加上其自身的值，即：

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

因为在minpath [k]计算之后行minpath [k + 1]将无用，我们可以简单地将minpath设置为1D数组，并迭代更新自身：

For the kth level:minpath[i] = min( minpath[i], minpath[i+1]) + triangle[k][i];

class Solution {public:    int minimumTotal(vector
   
    
      > &triangle) {        vector
     
       minNums = triangle[triangle.size() - 1];    //先将数组初始化为最后一行        for (int i = triangle.size() - 2; i > - 1; --i)         //从倒数第二行计算            for (int j = 0; j <= i; ++j)                        //第i行就有i+1个元素   (行是从0开始计数)                minNums[j] = (minNums[j] < minNums[j + 1] ? minNums[j] : minNums[j + 1])    //从两个子节点中选择小的，加上当前节点的值就是最小和                        + triangle[i][j];        return minNums[0];    }};