Problem Description

Given a number triangle, where each number is placed above two numbers in the row below, find the maximum possible sum of a path starting from the top and moving to adjacent numbers on the row below until the base of the triangle is reached.

For example, consider the following triangle:

    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

The maximum path sum is 7 + 3 + 8 + 7 + 5 = 30.

Solution Approach

A straightforward recursive approach would explore all possible paths from the top to the bottom. However, this method is highly inefficient because it recalculates the sum for the same sub-triangles multiple times, leading to an exponantial time complexity.

To optimize, we can use Dynamic Programming (DP). The core idea is to store the results of subproblems to avoid redundant calculations. We can solve this problem by working from the botttom of the triangle upwards.

Let's define dp[i][j] as the maximum path sum starting from the element at row i and column j. The solution to our problem will be dp[0][0].

The recurrence relation is:

dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])

This means the maximum sum for the current position is its own value plus the maximum of the two possible sums from the row below.

The base case is the bottom row of the triangle, where the maximum sum is simply the value of the element itself:

dp[last_row][j] = triangle[last_row][j]

By filling the dp table from the bottom up, we can efficiently compute the final answer.

Implementation

The following C++ code implements this bottom-up dynamic programming approach. It uses a one-dimensionla array to store intermediate results, optimizing space complexity.

#include <iostream>
#include <algorithm> // For std::max
#include <vector>

void calculateMaxPathSum(int triangle[][10], int height) {
    // dp array to store maximum sums for the current row
    std::vector<int> dp(height, 0);

    // Initialize dp with the values of the bottom row of the triangle
    for (int j = 0; j < height; ++j) {
        dp[j] = triangle[height - 1][j];
    }

    // Iterate from the second-to-last row up to the top
    for (int i = height - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            // The maximum sum for the current position is its value plus the
            // maximum of the two adjacent values from the row below
            dp[j] = triangle[i][j] + std::max(dp[j], dp[j + 1]);
        }
    }

    // The first element of dp now holds the maximum path sum from the top
    std::cout << dp[0] << std::endl;
}