Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to achieve the triangle on C++". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

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.

This problem gives us a triangle of a two-dimensional array, and let's find a top-down path to make the path and the shortest. Well, after that problem, we should first consider brute force cracking. We can find that if we want to traverse all the paths, it can be factorial time complexity, ah, OJ must be destroyed, it is better to stop thinking as soon as possible. It is necessary to optimize the time complexity, ah, the examples given in the title can easily bias people and make people think that the greedy algorithm can solve the problem, because if you look at the red array in the problem example, choose the small number 3 below the root number 2, choose the small number 5 under 3, and choose the small number 1 under 5. Every time you choose the smaller one of the two adjacent numbers on the next floor, you seem to get the answer. In fact, the greedy algorithm can bring the local minimum, but can not guarantee the global minimum every time, it is very likely that the number at the bottom of the other branches suddenly becomes super small, but the greedy algorithm has cut off all the other branches. So in order to ensure that we can get the global minimum, dynamic planning Dynamic Programming is still the best choice. In fact, this problem is very similar to Dungeon Game, which is solved by DP. So in fact, we can not create a new dp array, but directly reuse the triangle array, we want to accumulate layer by layer, so that triangle [I] [j] is the smallest path sum from the top level to the (I, j) position, so how do we get the state transition equation? In fact, it is not difficult, because each node can only go down to the two numbers adjacent to it, so each position (I, j) can only come from the two positions adjacent to it at the upper level, that is, (imur1, jmur1) and (iMuth1, j), then the state transfer equation is:

Triangle [I] [j] = min (Triangle [I-1] [j-1], triangle [I-1] [j])

Let's start with the second line, and notice that the numbers on both sides are directly assigned to the boundary value of the previous row, so in the end, we just need to find the number with the lowest value at the bottom, which is the global minimum path sum. The code is as follows:

Solution 1:

Class Solution {public: int minimumTotal (vector& triangle) {for (int I = 1; I

< triangle.size(); ++i) { for (int j = 0; j < triangle[i].size(); ++j) { if (j == 0) { triangle[i][j] += triangle[i - 1][j]; } else if (j == triangle[i].size() - 1) { triangle[i][j] += triangle[i - 1][j - 1]; } else { triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]); } } } return *min_element(triangle.back().begin(), triangle.back().end()); }}; 这种方法可以通过OJ，但是毕竟修改了原始数组triangle，并不是很理想的方法。在网上搜到一种更好的DP方法，这种方法复制了三角形最后一行，作为用来更新的一位数组。然后逐个遍历这个DP数组，对于每个数字，和它之后的元素比较选择较小的再加上面一行相邻位置的元素做为新的元素，然后一层一层的向上扫描，整个过程和冒泡排序的原理差不多，最后最小的元素都冒到前面，第一个元素即为所求。代码如下： 解法二： class Solution {public: int minimumTotal(vector& triangle) { vector dp(triangle.back()); for (int i = (int)triangle.size() - 2; i >

= 0;-- I) {for (int j = 0; j)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.