Maximum Sum Descent

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.
If the triangle only has a few rows, you may try to solve the puzzle by yourself. To this end, you can hide the solution and also the maximum sum that can be achieved.


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


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].
[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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.

Related Curriculum Standards

US Common Core State Standards, Mathematics

Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2018 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+