Details

This is puzzle number 62 in [1]. As in the book, the optimal path is found here by using dynamic programming. Let the centers of the cells be at points , , . The robot starts at and ends at . Let be 1 if there is a coin at and 0 otherwise. Let be the largest number of coins the robot can pick up and bring to . The task is to maximize .

The robot can reach the point either from below—that is, from —or from the left, . The largest number of coins that can be brought to these points are and , respectively. Thus, the largest number of coins the robot can bring to is the maximum of these two numbers plus . So, , , , . In addition, , , , and , .

After we have coded these formulas, we simply ask for the value of and we know the maximum number of coins that can be picked up! Mathematica does all the recursive calculations for us. 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.

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.