【Triangle 】cpp

题目：

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

代码：

class Solution {

public:

    int minimumTotal(vector<vector<int> > &triangle) {

            if (triangle.size()<) return ;

            int min_sum = triangle[][];

            for ( int i = ; i<triangle.size(); ++i )

            {

                for (int j = ; j<triangle[i].size(); ++j )

                {

                    if (j==triangle[i].size()-)

                    {

                        triangle[i][j] += triangle[i-][j-];

                        min_sum = std::min(min_sum, triangle[i][j]);

                    }

                    else if ( j== )

                    {

                        triangle[i][] += triangle[i-][];

                        min_sum = triangle[i][j];

                    }

                    else

                    {

                        triangle[i][j] += std::min(triangle[i-][j-], triangle[i-][j]);

                        min_sum = std::min(min_sum, triangle[i][j]);

                    }

                }

            }

            return min_sum;

    }

};

tips：

这种做法时间复杂度O(n)，空间复杂度O(1)。

思路很简单，就是遍历每层元素的同时，把这一个元素的值更新为走到该位置的最小路径和。

min_sum这个遍历记录当前最小值，其实只有当遍历到最后一层的时候才有用，偷懒就没有改动了。

但是有个缺点就是把原来的triangle的结构都破坏了，研究一下用O(n)额外空间，但不破坏原有triangle的做法。

=======================================

似乎脑子里有印象：遍历每层数组的时候，可以从后往前算，可以比较顺畅。顺着思路，就写了下面的代码，不破坏triangle的原有结构，也可以在O(n)额外空间的条件下AC。

class Solution {

public:

    int minimumTotal(vector<vector<int> > &triangle) {

            if (triangle.size()<) return ;

            vector<int> extra(triangle.size(),INT_MAX);

            extra[] = triangle[][];

            for ( int i = ; i<triangle.size(); ++i )

            {

                for ( int j = triangle[i].size()-; j>=; --j )

                {

                    if ( j== )

                    {

                        extra[j] = triangle[i][j] + extra[];

                    }

                    else

                    {

                        extra[j] = triangle[i][j] + std::min(extra[j-], extra[j]);

                    }

                }

            }

            int min_sum = extra[];

            for ( int i = ; i < extra.size(); ++i ) min_sum = std::min(min_sum, extra[i]);

            return min_sum;

    }

};

tips：

这里开一个额外vector（即extra），大小为n，数组元素初值都设为INT_MAX（后面解释为什么要设为INT_MAX）。

extra用来存放“到当前层的各个位置的最短路径长度和是多少”。

为什么遍历每层都要从后往前遍历呢？

举例说明如下：

以原题给的case为例

i = 1时

extra == [2,INT_MAX...]

triangle[1] == [3,4]

观察两种遍历triangle[1]的方向：

a) 先遍历triangle[1][0]则更新extra[0]为5，即extra == [5,INT_MAX...]

b) 这时，再遍历triangle[1][1]，判断extra[0]与extra[1]哪个小，再与triangle[1][1]相加，再赋值给extra[1]。

这里问题就凸显出来了，此时extra[0]已经不是最开始的2了，已经被我们更新过后丢掉了（此时可以采用补救措施，例如添加一个中间变量tmp之类的）。

现在换一种思路，改变遍历triangle[1]的方向

a) 遍历triangle[1][1]，则更新extra[1]为6

b) 这时再遍历triangle[1][0]，更新extra[0]为extra[0]+triangle[1][0]=5；结果正确。

这样对比就可以看出来从后向前遍历的好处，因为下一层的数组总比上一层的数组多出来一个元素；因此再更新时，先更新extra的最后一个位置并没有影响到上一轮extra得到的结果（于是也就不用什么tmp中间变量之类的了）。

还有一个细节没有说：为啥初始化extra的时候都初始化为INT_MAX呢？这是为了代码的优雅性。

通过题意我们可以知道，其实每层的最后一个元素j只能由上一层的的最后一个元素j-1得来。

为了保持“extra[j] = triangle[i][j] + std::min(extra[j-1], extra[j]);”的优雅性，因此初始化为INT_MAX；如果j==triangle[i].size()-1的时候，我们已经知道一定是选择extra[j-1]而不是extra[j]，因为此时的extra[j]就是INT_MAX。

这样一来，只用处理j==0的一种corner case了。

=================================

看到一种更屌爆的做法，完全不用判断各种corner case，思路如下：

从下往上遍历，牺牲triangle的原有结构。

======================================

第二次过这道题，用O(n)复杂度，单独处理最左边的元素。

class Solution {

public:

    int minimumTotal(vector<vector<int>>& triangle) {

            if ( triangle.empty() ) return ;

            vector<int> minPath(triangle.size(),INT_MAX);

            minPath[] = triangle[][];

            for ( int i=; i<triangle.size(); ++i )

            {

                for ( int j=triangle[i].size()-; j>; --j )

                {

                    minPath[j] = min(minPath[j-], minPath[j]) + triangle[i][j];

                }

                minPath[] += triangle[i][];

            }

            int ret = minPath[];

            for ( int i=; i<minPath.size(); ++i ) ret = min(ret, minPath[i]);

            return ret;

    }

};

巴特西

【Triangle 】cpp

最新文章

热门文章