We have a 3x3 grid with the following values:
1 3 4
7 2 1
4 1 8
A person starts on the leftmost column and can then move either northeast, east or southeast. Now I have to find the optimal path through this grid. The starting point can be anywhere on the leftmost column. In this case the answer was 17 because the optimal path was 7->2->8. I would like to know how to compute this optimal path and how to compute it for larger grids.
Thanks!
You can solve this problem with a bottom-up approach, or rather right-to-left in this case.
The last column is the end point of the path. Now consider the second but last row. You can determine the potential score from each cell s[i][j] by the cell's score a[i][j] plus the maximum potential score of the adjacent cells to the east:
s[i][j] = a[i][j] + max(s[i - 1][j + 1], s[i][j + 1], s[i + 1][j + 1])
If you do that for cells further to the west, you consider the already accumulated values of the cells further east. The optimal path with maximum score starts at the maximum accumulated value s in the first column. From there you go east by picking the best adjacent value.
The accumulated matrix s for your example is:
| 1 3 4 | | 11 7 4 |
a = | 7 2 1 | s = | 17 10 1 |
| 4 1 8 | | 14 9 8 |
This approach where you accumulate the optimum from right to left is essentially the same as working from left to right where already calculated values are memoized in s.