Dynamic Programming: Triangle (Fixed Starting Point & Variable Ending Point)

This chapter explores DP on Grids: Triangle Path Sums, focusing on problems characterized by a fixed starting point and a variable ending point. Unlike previous grid problems where movement was restricted to fixed corners ((0, 0) to (n-1, m-1)), triangular grid structures allow multiple valid termination destinations along the bottom row, necessitating a shift in our recursive and tabular mental models.

1. Problem Statement & Grid Topology

We are given a triangular array of numbers (a right-angled triangle) with $n$ rows, where the $i$-th row contains $i + 1$ elements. Our objective is to find the minimum path sum from the top row down to any element in the bottom row.

Key Rules of Movement:

• When standing at index j in row i, you can move to one of two adjacent positions in row i + 1:
  1. Directly Down: Index j in row i + 1 (i + 1, j)
  2. Diagonally Right: Index j + 1 in row i + 1 (i + 1, j + 1)

Visualizing the Triangle (4 Rows Example)

Row 0:        [ 1 ]
Row 1:      [ 2, 3 ]
Row 2:    [ 3, 6, 7 ]
Row 3:  [ 8, 9, 10, 10 ]

• Starting Point: Fixed at the top element (0, 0).
• Ending Point: Variable. You can terminate at any column index in the final bottom row (n - 1).

2. Why Greedy Solutions Fail

Real-Life Analogy: The Mountain Descent

Imagine descending a treacherous mountain shaped like a triangle where each step costs a certain toll. If you use a greedy strategy—always picking the smaller local number immediately below or diagonal to you—you might make a short-sighted choice early on (e.g., picking a 2 instead of a 3) that traps you later in a region of overwhelmingly high numbers.

• Uniformity Violation: Greedy algorithms rely on local uniformity or monotonic trends. In grid problems with erratic numeric distributions, local optimization leads to suboptimal global outcomes.
• Conclusion: We must evaluate all possible paths to guarantee the absolute minimum sum.

3. Direction of Recursion: Top-Down vs. Bottom-Up

In standard grid problems where the destination was fixed at the bottom-right corner (n-1, m-1), we usually started our recursion from the bottom and worked our way back to (0, 0).

Why Bottom-Up Fails Logically Here:

If we attempted to start from the bottom, we would have multiple valid ending/starting points across all columns of the last row. We would have to spawn multiple recursive calls from every single element in row n-1, complicating our base cases and entry points.

The Superior Approach: Top-Down Traversal

• Start: f(0, 0) (representing the minimum path sum from the top element to any valid column in the last row).
• Rationale: By anchoring our start at the unique apex (0, 0), we can cleanly branch downward and let the base case handle the variable endings when we hit row n - 1.

4. Designing the Recursive Function

To write a complete recursive solution, we follow the standard 3-step dynamic programming recipe:

1. Express in Indices: Represent state as f(i, j) where i is the current row and j is the current column.
2. Explore All Paths: Try moving down (i + 1, j) and diagonally right (i + 1, j + 1).
3. Take the Minimum: Return the minimum of the two explored paths plus the current cell's value.

Base Cases & Boundary Conditions

• Destination Reached: When i == n - 1, we have arrived at the bottom row. We simply return the value of the triangle at (n - 1, j).
• Out of Bounds: Because we only ever move straight down (j) or diagonally right (j + 1), we will never exceed the right boundary of the triangle's valid column indices. Thus, no extra out-of-bounds checks are needed.

Recursive Implementation (C++)

int f(int i, int j, vector<vector<int>>& triangle, int n) {
    // Base Case: Reached the last row
    if (i == n - 1) {
        return triangle[i][j];
    }
    
    // Explore Down Path
    int down = triangle[i][j] + f(i + 1, j, triangle, n);
    
    // Explore Diagonal Right Path
    int diagonal = triangle[i][j] + f(i + 1, j + 1, triangle, n);
    
    return min(down, diagonal);
}

• Time Complexity: $O(2^n)$ (Exponential due to duplicate branching for each cell).
• Space Complexity: $O(n)$ (Recursion stack space proportional to the height of the triangle).

5. Overlapping Subproblems & Memoization

Drawing the recursion tree reveals that many states f(i, j) are computed multiple times. To eliminate this redundancy, we introduce a DP memoization table of size $n \times n$ initialized to -1.

Memoized Implementation (C++)

int f(int i, int j, vector<vector<int>>& triangle, int n, vector<vector<int>>& dp) {
    if (i == n - 1) return triangle[i][j];
    
    if (dp[i][j] != -1) return dp[i][j];
    
    int down = triangle[i][j] + f(i + 1, j, triangle, n, dp);
    int diagonal = triangle[i][j] + f(i + 1, j + 1, triangle, n, dp);
    
    return dp[i][j] = min(down, diagonal);
}

// Inside main caller:
vector<vector<int>> dp(n, vector<int>(n, -1));
return f(0, 0, triangle, n, dp);

• Time Complexity: $O(n^2)$ (Number of states in a triangular grid $\approx \frac{n(n+1)}{2}$).
• Space Complexity: $O(n^2)$ (DP table) + $O(n)$ (Recursion stack space).

6. Converting to Tabulation (Bottom-Up DP)

To avoid Stack Overflow and Time Limit Exceeded (TLE) errors on strict online judges, we convert the top-down memoized solution into an iterative tabulation approach.

Tabulation Strategy:

1. Base Case Initialization: Fill the last row of the DP table (n - 1) directly with the values from the triangle's last row.
2. Nested Loops: Iterate row i backwards from n - 2 down to 0. For each row, iterate column j from 0 up to i (since row i has i + 1 elements).
3. State Transition: Apply the recurrence relation using previously computed values from row i + 1.

Tabulation Implementation (C++)

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // Step 1: Initialize the base case (last row)
    for (int j = 0; j < n; j++) {
        dp[n - 1][j] = triangle[n - 1][j];
    }
    
    // Step 2: Bottom-up filling from second-last row up to row 0
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            int down = triangle[i][j] + dp[i + 1][j];
            int diagonal = triangle[i][j] + dp[i + 1][j + 1];
            
            dp[i][j] = min(down, diagonal);
        }
    }
    
    // Step 3: Top cell holds the global minimum path sum
    return dp[0][0];
}

7. Space Optimization

Analyzing our tabulation dependency, computing the values for row i only requires data from row i + 1. We do not need to store the entire $n \times n$ DP table in memory.

Optimization Strategy:

• Maintain two single-dimensional vectors:
  1. front: Represents row i + 1 (the row below us).
  2. curr: Represents row i (the row we are currently calculating).
• Once row i is fully computed, curr becomes the new front for the next iteration.

Space-Optimized Implementation (C++)

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<int> front(n, 0);
    
    // Initialize front with the last row values
    for (int j = 0; j < n; j++) {
        front[j] = triangle[n - 1][j];
    }
    
    // Iterate upwards
    for (int i = n - 2; i >= 0; i--) {
        vector<int> curr(n, 0);
        for (int j = 0; j <= i; j++) {
            int down = triangle[i][j] + front[j];
            int diagonal = triangle[i][j] + front[j + 1];
            
            curr[j] = min(down, diagonal);
        }
        front = curr; // Shift reference rows upward
    }
    
    return front[0];
}

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n)$ (Reduced from $O(n^2)$ by maintaining only two active row arrays).

8. Summary & Key Takeaways

• Variable Ending Points: When destination points are variable across a boundary (like the bottom row of a triangle), anchoring your recursion at a fixed start point (0, 0) is far more intuitive than starting from multiple targets.
• Grid Topology: Triangular grids feature rows where the $i$-th row contains $i + 1$ columns, restricting loop boundaries dynamically (j <= i).
• Absence of Out-of-Bounds: Because allowed movements are strictly downward (i+1, j) and diagonal (i+1, j+1), bounds checking is greatly simplified compared to standard rectangular grids.
• Greedy Failure: Local minimal selections fail because triangle values lack monotonic uniformity.
• Memoization Translation: Top-down recursion computes states redundantly; adding an $n \times n$ memoization table cuts complexity from exponential $O(2^n)$ down to polynomial $O(n^2)$.
• Tabulation Rule of Thumb: Tabulation works in the reverse direction of recursion. Since recursion goes from 0 to n-1, tabulation builds answers from n-2 back up to 0.
• Space Compression: Because row computations only depend on the immediately adjacent lower row, space complexity can be optimized from $O(n^2)$ to $O(n)$ using rolling arrays (front and curr).