The Manhattan Tourist Problem Revisited

Length of the longest path in a rectangular grid

You should now be ready to implement an algorithm solving the Manhattan Tourist Problem. The following pseudocode computes the length of the longest path to node (i, j) in a rectangular grid and is based on the observation that the only way to reach node (i, j) in the Manhattan Tourist Problem is either by moving south (↓) from (i − 1, j) or east (→) from (i, j − 1).

  SouthOrEast(i, j)
   if i = 0 and j = 0
     return 0
   x ← −∞, y ← −∞
   if i > 0
     x ← SouthOrEast(i − 1, j) + weight of the vertical edge into (i, j)
   if j > 0
     y ← SouthOrEast(i, j − 1) + weight of the horizontal edge into (i, j)
   return max{x, y}

STOP and Think: How many times is SouthOrEast(3, 2) called in the computation of SouthOrEast(9, 7)?

Reframing the algorithm using dynamic programming

Similarly to RecursiveChange, SouthOrEast suffers from a huge number of recursive calls, and we need to reframe this algorithm using dynamic programming. Remember how DPChange worked from small instances upward? To find the length of a longest path from source (0, 0) to sink (n, m), we’ll first find the lengths of longest paths from the source to all nodes (i, j) in the grid, expanding slowly outward from the source.

At first glance, you may think that we’ve created additional work for ourselves by solving $n \times m$ different problems instead of a single problem. Yet SouthOrEast also solves all these smaller problems, just as RecursiveChange and DPChange both computed MinNumCoins(m) for all values of $m < money$ ...