Swipe to show menu

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))

Switch to desktop for real-world practiceContinue from where you are using one of the options below

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

Problem C. Minimum Path in Triangle

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))

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Everything was clear?

Thanks for your feedback!

Swipe to show menu

Problem C. Minimum Path in Triangle

Awesome!

Problem C. Minimum Path in Triangle

Awesome!