Learn Problem C. Minimum Path in Triangle

The key to the solution is forming all possible minimum-cost paths from top to bottom row. You can not be sure which one will have minimum cost, so let's traverse a triangle and update values in the cells:

triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]: thats how you can reach cell [i, j]` with min cost
triangle[i][0] += triangle[i-1][0], triangle[i][i-1] += triangle[i-1][i-1] : extreme cases (number of columns in each row is equal to number of row).

After updating, choose the minimum path cost, which is in the last row.


              1234567891011121314151617181920
            
def minPath(triangle):
  for i in range(1, len(triangle)):
    for j in range(i+1):
      small = 10000000
      if j > 0:
        small = triangle[i-1][j-1]
      if j < i:
        small = min(small, triangle[i-1][j])
      triangle[i][j] += small
  return min(triangle[-1])  
       
triangle = [[90],
 [72, 6],
 [3, 61, 51],
 [90, 70, 23, 100],
 [79, 92, 72, 14, 1],
 [7, 97, 29, 100, 93, 93],
 [52, 95, 21, 36, 69, 69, 14],
 [33, 82, 20, 37, 79, 83, 21, 45]]
print(minPath(triangle))

Everything was clear?

Thanks for your feedback!

Section 3. Chapter 3

single

Ask AI

Ask anything or try one of the suggested questions to begin our chat

Swipe to show menu

triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]: thats how you can reach cell [i, j]` with min cost
triangle[i][0] += triangle[i-1][0], triangle[i][i-1] += triangle[i-1][i-1] : extreme cases (number of columns in each row is equal to number of row).