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
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
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.
Each node can go down only the two numbers adjacent to it, so each position (i, j) can only come from the two positions adjacent to it in the upper layer, which is (i-1 , j-1) and (i-1, j) these two positions, then the state transition equation is:
We update from the second line. Note that the numbers on both sides are directly assigned to the boundary value of the previous line. In the end, we only need to find the number with the smallest value at the bottom layer, which is the global smallest path sum.