Hi everybody,
Today we can discuss a Leetcode question. Question :
120. 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).
We can start to understand the problem.
First, we need to understand this question is a Dynamic Problem question. How?
1- We have a triangle.
2-) We need to traverse this trangle
3-) We can compute the min path through the Triangle.
Second, we need to use an extra space like a 2 Dimensional array store to compute the adjacency number on the row below.
Third, in the base case traverse and general traverse case. The base case will traverse fill the left side of our 2D Array. The general traverse case will fill the inside of our second 2 D Array table.
After we need to sum the left and right sides of the Triangle and we can pass the left and right sides of our 2D Table.
Like :
Original Triangle :
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
Fill the left and right side of Table :
[
[2, 0, 0, 0],
[5, 6, 0, 0],
[11, 0, 13, 0],
[15, 0, 0, 16]]
for left side :
2+3 = 5
2+4 = 6
2+3 + 6= 11
2+3 + 6 + 4= 15
After we need to fill 2D inside cells. We can use the Pascal Triangle Equation in this part. We can get min upper cells and we can sum the current triangle cell.
f(i,j) = min(col[i-1][j-1], col[i-1][j]) + triangle[i][j]Fill the inside Table :
[
[2, 0, 0, 0],
[5, 6, 0, 0],
[11, 10, 13, 0],
[15, 11, 18, 16]
]
Some examples :
table[2,1] = min(5,6) + 5 = 10
table[3,1] = min(11,10) + 1 = 11
Our Code:
Complexities
T(N) = O(rowNumbers²)
1. row = 1
second row = 2 cells
3. row = 3 cells
1+2+3….+ r = r(r+1)/2 = O(r²)
S(N) = O(rowNumbers²) = We need to store each number that we update in triangle.
