Introduction

Dynamic Programming (DP) is a powerful algorithmic technique used to solve optimization problems. The "Pyramids" problem is one of the classic examples that highlight the elegance and efficiency of dynamic programming. The problem involves finding the maximum path sum in a triangle (or pyramid-shaped structure) where each number along the path must be added to obtain the largest sum from top to bottom.

Problem Description

In this problem, you are given a triangle of numbers. You must start from the top of the triangle and move to an adjacent number on the row immediately below until you reach the base. The challenge is to find the path that yields the maximum sum.

Triangle Example

Consider the following triangle:

1      7
2     6 3
3    3 8 5
4   11 2 10 9

Possible paths from the top to the base include:

1. 7 → 6 → 3 → 11
2. 7 → 6 → 8 → 2
3. 7 → 3 → 8 → 10

The task is to calculate the maximum possible sum along these paths.

Dynamic Programming Approach

Key Concept

The dynamic programming approach for solving the pyramids problem involves building a solution bottom-up. Starting from the base of the pyramid, you calculate the maximum sum for each subtree of the pyramid. This effectively transforms the problem into solving smaller subproblems and using those solutions to construct the answer for the larger problem.

Step-by-Step Solution

1. Initialize the Base: Begin by initializing the DP table with the values of the last row of the pyramid. These represent the maximum sums if those nodes were the bottom of their paths.
2. Build Upwards: Move upwards row by row. For each element in a row, calculate the maximum sum by adding the element to the maximum of the two sums below it.
3. Final Result: After processing all rows, the top element of your DP table will hold the maximum path sum from top to bottom.

Example Walkthrough

Given the previous triangle, let's illustrate with dynamic programming:

1. Initialize last row:

   11 2 10 9  (initial)

1. Update values above by adding maximum of the two possible values below:
   • For third row:
     • 3 + max(11, 2) = 14
     • 8 + max(2, 10) = 18
     • 5 + max(10, 9) = 15 Resulting DP for second row:

   14 18 15

1. Continue to second row:
   • For second row:
     • 6 + max(14, 18) = 24
     • 3 + max(18, 15) = 21 Resulting DP for first row:

   24 21

1. Finally, calculate for the top of the pyramid:
   • 7 + max(24, 21) = 31

The maximum path sum is 31.

Implementation

Here is a Python implementation of the pyramids dynamic programming solution:

1def max_path_sum(triangle):
2    # Start from the second last row from the bottom and go upwards
3    for row in range(len(triangle) - 2, -1, -1):
4        for col in range(len(triangle[row])):
5            # Update each element with the max sum path
6            triangle[row][col] += max(triangle[row + 1][col], triangle[row + 1][col + 1])
7
8    # The top element now contains the maximum path sum
9    return triangle[0][0]
10
11# Example usage
12triangle = [
13    [7],
14    [6, 3],
15    [3, 8, 5],
16    [11, 2, 10, 9]
17]
18
19print("Maximum path sum is:", max_path_sum(triangle))

Summary

Below is a summary table highlighting the key points of the dynamic programming approach for the pyramids problem.

Conclusion

Dynamic programming offers a methodical approach to solving optimization problems such as the pyramids problem. By breaking down the problem into manageable subproblems and solving each efficiently, we can ensure optimal solutions with improved performance. This example illustrates the strategic thinking required to leverage dynamic programming in algorithm design.