首页 > 代码库 > 【LeetCode】Triangle

【LeetCode】Triangle

2024-07-04 05:19:20   232人阅读

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.

 

像树这样的数据结构，直觉肯定是递归，几行就搞定。可惜TLE。不过程序应该是正确的。

class Solution {
public:
    int min(int a, int b)
    {
        return a<b?a:b;
    }
    int sum(vector<vector<int> > &triangle, int index, int level)
    {
        if(level == triangle.size()-1)
            return triangle[level][index];
        else
            return triangle[level][index] + min(sum(triangle, index, level+1), sum(triangle, index+1, level+1));
    }
    int minimumTotal(vector<vector<int> > &triangle) 
    {
        if(triangle.empty())
            return 0;
        else
            return sum(triangle, 0, 0);
    }
};

 

改进过程：

其实这类尾递归转换为迭代方式很简单，就是把结果传递下去，而不是通过return返回上来。

稍微改一下就行，核心思想是，每个元素存放从root到当前元素的最小和。

等计算完最后一行，遍历一遍找出最小的元素即可。

class Solution 
{
public:
    int min(int a, int b)
    {
        return a<b?a:b;
    }
    int minimumTotal(vector<vector<int> > &triangle) 
    {
        if(triangle.size() == 0)
            return 0;
        else if(triangle.size() == 1)
            return triangle[0][0];
        else
        {
            for(vector<vector<int> >::size_type st1 = 1; st1 < triangle.size(); st1 ++)
            {
                for(vector<int>::size_type st2 = 0; st2 < triangle[st1].size(); st2 ++)
                {
                    if(st2 == 0)
                        triangle[st1][st2] = triangle[st1][st2] + triangle[st1-1][st2];
                    else if(st2 == triangle[st1].size()-1)
                        triangle[st1][st2] = triangle[st1][st2] + triangle[st1-1][st2-1];
                    else
                        triangle[st1][st2] = triangle[st1][st2] + min(triangle[st1-1][st2], triangle[st1-1][st2-1]);
                }
            }
            int size = triangle.size();
            int result = triangle[size-1][0];
            for(vector<int>::size_type st = 1; st < triangle[size-1].size(); st ++)
                if(triangle[size-1][st] < result)
                    result = triangle[size-1][st];

            return result;
        }
    }
};

 

上述是使用top-down方法。看了一下Discussion发现其实可以简化一下，去掉最后一次遍历过程，使用bottom-up方法将最小值汇聚到root

class Solution 
{
public:
    int minimumTotal(vector<vector<int> > &triangle) 
    {
        if(triangle.size() == 0)
            return 0;
        for(vector<vector<int> >::size_type st1 = triangle.size()-1; st1 > 0; st1 --)
        {
            for(vector<int>::size_type st2 = 0; st2 < triangle[st1].size()-1; st2 ++)
            {
                if(triangle[st1][st2] < triangle[st1][st2+1])
                    triangle[st1-1][st2] += triangle[st1][st2];
                else
                    triangle[st1-1][st2] += triangle[st1][st2+1];
            }
        }
        return triangle[0][0];
    }
};

 

以上都是in-place的做法。

但是按照题意O(n)空间复杂度，其实可以用类似的方法将中间结果保存在开辟的空间中，不改变输入数据。

 


联系
我们