Problem Description

You are given a triangular array of numbers where you need to find the minimum sum path from the top to the bottom of the triangle.

Starting from the top of the triangle, at each step you can move to one of two adjacent numbers in the row directly below. Specifically:

• If you are currently at position i in a row, you can move to either position i or position i + 1 in the next row

Your goal is to find the path from top to bottom that results in the minimum possible sum of all numbers along that path.

For example, if you have a triangle like:

     2
    3 4
   6 5 7
  4 1 8 3

From the top 2, you could go to either 3 or 4 in the second row. If you choose 3, from there you could go to either 6 or 5 in the third row, and so on. The problem asks you to find which path through all these choices gives you the smallest total sum.

The solution uses dynamic programming, working from bottom to top. The approach calculates f[i][j] which represents the minimum path sum from position (i,j) to the bottom of the triangle. The recurrence relation is:

f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j]

This means the minimum path sum from any position equals the value at that position plus the minimum of the two possible paths below it. The final answer is f[0][0], which gives the minimum path sum starting from the top of the triangle.

Intuition

The key insight is to think about this problem backwards - instead of trying to find the best path from top to bottom, we can find the best path from each position to the bottom.

Why work backwards? When we start from the top and try to make decisions, we don't know what lies ahead. At each step, we might choose a path that seems good locally but leads to larger numbers later. However, if we start from the bottom, we already know all the information we need to make optimal decisions.

Consider any position in the triangle. From that position, we need to reach the bottom, and we want the minimum sum to get there. If we already know the minimum sum from each of the two positions below us to the bottom, then our decision becomes simple: we choose the path with the smaller sum and add our current value to it.

This naturally leads to a bottom-up dynamic programming approach. Starting from the second-to-last row, for each position we ask: "What's the minimum cost to reach the bottom from here?" The answer is our current value plus the minimum of the two paths available from the positions below us.

By the time we work our way up to the top of the triangle, we've computed the minimum path sum from every position to the bottom. The value at the top position f[0][0] gives us the minimum path sum for the entire triangle.

The beauty of this approach is that we're building up the solution from smaller subproblems (positions closer to the bottom) to larger ones (positions closer to the top), ensuring that at each step we're making the globally optimal choice based on complete information about what lies below.

Solution Approach

The implementation uses a bottom-up dynamic programming approach with a 2D array to store intermediate results.

Data Structure Setup: We create a 2D array f of size (n+1) × (n+1) where n is the number of rows in the triangle. The extra row and column (filled with zeros) act as padding to handle boundary cases gracefully when we look at positions f[i+1][j] and f[i+1][j+1] from the last row.

Bottom-Up Traversal: We iterate through the triangle from bottom to top:

• Outer loop: i goes from n-1 down to 0 (processing each row from bottom to top)
• Inner loop: j goes from 0 to i (processing each element in the current row)

State Transition: For each position (i, j), we apply the recurrence relation:

f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j]

This calculates the minimum path sum from position (i, j) to the bottom by:

1. Looking at the two possible next positions: (i+1, j) and (i+1, j+1)
2. Taking the minimum of their already-computed path sums
3. Adding the current position's value triangle[i][j]

Why This Works:

• When we start at row n-1 (the last row), the values below are all zeros from our padding, so f[n-1][j] simply equals triangle[n-1][j]
• As we move up, each position's minimum path sum is computed based on the already-calculated values below it
• By the time we reach the top f[0][0], we have the minimum path sum for the entire triangle

Space Optimization Note: While this solution uses O(n²) space, it can be optimized to O(n) by using a 1D array and updating it in place, since we only need values from the row directly below the current one.

Example Walkthrough

Let's trace through the algorithm with a small triangle:

   2
  3 4
 6 5 7

Step 1: Initialize the DP table We create a 4×4 table f (n=3, so size is n+1):

f = [[0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0]]

Step 2: Process bottom row (i=2)

• For j=0: f[2][0] = min(f[3][0], f[3][1]) + triangle[2][0] = min(0, 0) + 6 = 6
• For j=1: f[2][1] = min(f[3][1], f[3][2]) + triangle[2][1] = min(0, 0) + 5 = 5
• For j=2: f[2][2] = min(f[3][2], f[3][3]) + triangle[2][2] = min(0, 0) + 7 = 7

Table after this step:

f = [[0, 0, 0, 0],
     [0, 0, 0, 0],
     [6, 5, 7, 0],
     [0, 0, 0, 0]]

Step 3: Process middle row (i=1)

• For j=0: f[1][0] = min(f[2][0], f[2][1]) + triangle[1][0] = min(6, 5) + 3 = 5 + 3 = 8
• For j=1: f[1][1] = min(f[2][1], f[2][2]) + triangle[1][1] = min(5, 7) + 4 = 5 + 4 = 9

Table after this step:

f = [[0, 0, 0, 0],
     [8, 9, 0, 0],
     [6, 5, 7, 0],
     [0, 0, 0, 0]]

Step 4: Process top row (i=0)

• For j=0: f[0][0] = min(f[1][0], f[1][1]) + triangle[0][0] = min(8, 9) + 2 = 8 + 2 = 10

Final table:

f = [[10, 0, 0, 0],
     [8,  9, 0, 0],
     [6,  5, 7, 0],
     [0,  0, 0, 0]]

Result: The minimum path sum is f[0][0] = 10, which corresponds to the path: 2 → 3 → 5 (sum = 2 + 3 + 5 = 10).

The algorithm correctly identifies that going left at each step (2 → 3 → 5) gives a smaller sum than other paths like 2 → 4 → 5 (sum = 11) or 2 → 4 → 7 (sum = 13).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²) where n is the number of rows in the triangle. The algorithm uses two nested loops - the outer loop iterates through all n rows, and for each row i, the inner loop iterates i + 1 times. The total number of operations is 1 + 2 + 3 + ... + n = n(n+1)/2, which simplifies to O(n²).

Space Complexity: O(n²) for the current implementation. The code creates a 2D array f with dimensions (n+1) × (n+1), consuming O(n²) extra space. However, as the reference answer suggests, this can be optimized to O(1) by modifying the triangle array in-place instead of creating a separate f array. The in-place modification would work because once we compute the minimum path sum for a position, we don't need the original value anymore as we're working from bottom to top.

Common Pitfalls

1. Index Out of Bounds When Not Using Padding

A frequent mistake is attempting to implement the bottom-up approach without proper padding, leading to index errors when accessing dp[i+1][j+1] at the rightmost element of each row.

Incorrect Implementation:

# This will cause IndexError
dp = [[0] * len(triangle[i]) for i in range(len(triangle))]
for row in range(num_rows - 1, -1, -1):
    for col in range(row + 1):
        # When col = row, dp[row + 1][col + 1] is out of bounds!
        dp[row][col] = min(dp[row + 1][col], dp[row + 1][col + 1]) + triangle[row][col]

Solution: Either use padding as shown in the original solution, or handle the last row as a special case:

# Initialize with the last row
dp = [triangle[-1][:]]  # Copy the last row
for row in range(num_rows - 2, -1, -1):
    dp.append([0] * (row + 1))
    for col in range(row + 1):
        dp[row][col] = min(dp[row + 1][col], dp[row + 1][col + 1]) + triangle[row][col]

2. Modifying the Input Triangle Directly

Some developers try to save space by modifying the input triangle in-place, which can cause issues if the input should remain unchanged or if the solution needs to be run multiple times.

Problematic Approach:

# Modifying input directly - bad practice
for row in range(num_rows - 2, -1, -1):
    for col in range(row + 1):
        triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1])
return triangle[0][0]

Solution: Always create a separate data structure unless the problem explicitly allows in-place modification:

# Use a separate 1D array for space-efficient solution
dp = triangle[-1][:]  # Start with a copy of the last row
for row in range(num_rows - 2, -1, -1):
    for col in range(row + 1):
        dp[col] = min(dp[col], dp[col + 1]) + triangle[row][col]
return dp[0]

3. Incorrect Loop Boundaries

Getting the loop ranges wrong, especially the inner loop, is a common error. The inner loop should iterate from 0 to row (inclusive), not to num_rows.

Wrong Implementation:

for row in range(num_rows - 1, -1, -1):
    for col in range(num_rows):  # Wrong! Should be range(row + 1)
        dp[row][col] = min(dp[row + 1][col], dp[row + 1][col + 1]) + triangle[row][col]

This processes non-existent elements in the triangle since row i only has i+1 elements.

Solution: Always remember that row i in the triangle has exactly i+1 elements:

for row in range(num_rows - 1, -1, -1):
    for col in range(row + 1):  # Correct: iterate through valid positions only
        dp[row][col] = min(dp[row + 1][col], dp[row + 1][col + 1]) + triangle[row][col]