# Maximum Sum Descent

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

In this puzzle, we have numbers in a triangle. From each number, we can only go to one of the two numbers below the current number. The task is to find a path among the numbers from the top to the bottom that maximizes the sum of the numbers along the path.

[more]
Contributed by: Heikki Ruskeepää (April 2012)

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

This is puzzle number 20 in [1]. As in this book, the optimal path is here found by using dynamic programming. Let be the number in the row. Let be the largest sum we can get by going from to . If the table of numbers has rows, the task is to find the index for which we get the largest . Clearly, , = 2, …, , = 2, …, . In addition, and .

After we have coded these formulas, we simply ask the value of , = 1, …, . The maximum of these numbers is the largest sum we can get. To get the optimal path, we also write down from where it is optimal to come to each . Note that often the optimal path is not unique.

Another puzzle from [1] that is solved by dynamic programming can be found from a Demonstration mentioned in the Related Links. For more about dynamic programming with *Mathematica*, see Section 23.5.2 in [2].

References

[1] A. Levitin and M. Levitin, *Algorithmic Puzzles*, New York: Oxford University Press, 2011.

[2] H. Ruskeepää, *Mathematica Navigator: Mathematics, Statistics, and Graphics*, 3rd ed., San Diego: Elsevier Academic Press, 2009.

## Permanent Citation