Triangle (Minimum Path Sum)

Welcome to a fascinating journey into the world of Data Structures and Algorithms! Today, we'll be exploring the Minimum Path Sum problem in a Triangle. Let's dive in!

Understanding the Problem

Imagine a triangle with numbers representing the sum of points on each vertex. Our goal is to find the minimum path sum from the topmost point to the bottommost point.

markdown

💡 Pro Tip: The idea is to choose the number that helps us reach the bottom with the least sum.

Breaking Down the Solution

The solution involves a dynamic programming approach, where we fill up the triangle iteratively, starting from the bottom.

Step 1

Fill up the last row:

markdown

   1
5
6  1
2  6  8

-> 8 (last number in the last row)

Step 2

Start from the second last row and fill up the numbers based on the minimum of the two options: the number from the corresponding position in the previous row or the number just above and to the left.

markdown

   1
5
6  1
2  6  8

(min(4, 7) + 2)
(min(3, 6) + 1)

Step 3

Continue filling up the triangle iteratively until we reach the top.

markdown

   1
5
6  1
2  6  8

(min(2, 7) + 5)
(min(1, 3) + 4)

Implementing the Solution (Python)

Now that we understand the concept, let's see how we can implement it in Python.

python

def minPathSum(triangle):
    for row in range(1, len(triangle)):
        for col in range(row, len(triangle[row])):
            triangle[row][col] += min(triangle[row - 1][col], triangle[row - 1][col - 1])

    return triangle[len(triangle) - 1][len(triangle[len(triangle) - 1]) - 1]

triangle = [[1], [3, 5], [7, 6, 1], [4, 2, 6, 8]]
print(minPathSum(triangle))

📝 Note: The time complexity of this solution is O(n^2) due to the double loop, but it's space-efficient as it only requires constant space.

Practice Time 🚀

Now that you've learned the basics, let's test your understanding with a quick quiz.

Keep learning, coding, and growing with CodeYourCraft! 🚀

In the next lesson, we'll delve deeper into other dynamic programming problems and explore their solutions! 🎯 Stay tuned!