Triangle - Solution & Explanation

Problem Overview: You are given a triangle array where each row has one more element than the previous. Starting at the top, move to adjacent numbers on the row below and compute the minimum path sum from top to bottom.

The key constraint: from index i in row r, you can only move to i or i+1 in row r+1. Brute forcing every path quickly explodes in complexity, so the problem naturally leads to dynamic programming where overlapping subproblems are reused.

Approach 1: Top-Down Dynamic Programming with Memoization (Time: O(n²), Space: O(n²))

Start from the top element and recursively explore the two valid moves to the next row. At each position (row, col), compute the minimum cost of continuing down the triangle. Without caching, the same subtrees get recomputed many times. Memoization fixes this by storing results in a DP table indexed by (row, col). When the recursion revisits a state, return the stored value instead of recomputing. This converts an exponential recursion into an efficient solution that processes each cell once.

The recursive relation is: triangle[row][col] + min(down, diagonal). This approach maps closely to the problem definition and is easy to reason about if you're comfortable with recursion.

Approach 2: Dynamic Programming Bottom-Up (Time: O(n²), Space: O(n))

Instead of starting from the top, work upward from the last row. The last row already represents the minimum path sums from those nodes to the bottom. Maintain a DP array initialized with the last row values. Then iterate from the second-last row upward, updating each position with triangle[row][col] + min(dp[col], dp[col+1]). Each update represents choosing the cheaper of the two reachable children.

This method processes the triangle level by level and reuses a single array, reducing memory usage to O(n) where n is the width of the bottom row. Since every element is visited once, the total runtime is O(n²). The approach relies on simple iteration and fits naturally with array traversal.

Recommended for interviews: The bottom-up dynamic programming solution is usually expected. It runs in optimal O(n²) time with O(n) space and demonstrates strong DP intuition. Showing the recursive memoized version first can highlight how the problem decomposes into subproblems, but finishing with the bottom-up optimization signals deeper mastery.