用C ++中的解释找到三角解决方案中从上到下的最小路径

For example, given the following triangle
[
     [2],
    [3,5],
   [7,5,8],
  [5,1,9,4]
]

从上到下的最小路径总和为11（即2 + 3 + 5 + 1 = 11）。

后续问题：
如果您仅能使用O（n）额外空间来执行此操作，则奖励积分，其中n是三角形中的总行数。

此问题的解决方案可以通过两种方式解决：

1. 自上而下的方法
2. 自下而上的方法

C ++解决方案

#include<iostream>
#include<vector>
using namespace std;


int top_down_solution(vector<vector<int>> &triangle)
{
	//take a result vector of size of triangle and initialize with INT_MAX
    vector<int> result(triangle.size(), INT_MAX);

    //initialize the first element of result with the value at triangle[0][0]
    result[0] = triangle[0][0];

    //now starting from the index 1, go through all the level
    for (int i = 1; i < triangle.size(); i++)
    {
    	// this for loop represents the elements inside a level
        for (int j = i; j >= 1; j--)
        {
            result[j] = min(result[j - 1], result[j]) + triangle[i][j];
        }

        // as we are starting from index 1, add the elements from index 0 上  all the level.
        result[0] += triangle[i][0];
    }

    //c++ library function to get the min element inside a vector.
    return *min_element(result.begin(), result.end());
}


/*
	In bottom up approach,
	1. Start form the row above the bottom row [size()-2].
	2. Each level add the smaller number of two numbers with the current element i.e triangle[i][j].
	3. Finally get to the top with the smallest sum.
*/
int bottom_up_solution(vector<vector<int>>& triangle) 
{
    vector<int> res = triangle.back();

    for (int i = triangle.size()-2; i >= 0; i--) 
        for (int j = 0; j <= i; j++) 
            res[j] = triangle[i][j] + min(res[j], res[j+1]);

    return res[0];
}

int main() 
{ 
    vector<vector<int> > triangle{ 	{ 2 }, 
                            		{ 3, 9 }, 
                            		{ 1, 6, 7 } }; 
    cout <<"The minimum path sum from top to bottom using \"top down\" approach is = "<< top_down_solution(triangle)<<endl; 

    cout <<"The minimum path sum from top to bottom using \"bottom up\" approach is = "<< bottom_up_solution(triangle)<<endl; 


    return 0; 
}

输出：

The minimum path sum from top to bottom using "top down" approach is = 6
The minimum path sum from top to bottom using "bottom up" approach is = 6

该网站上可用的教程列表：