Consider a game on an nxm-sized grid. Each cell xi, j of the grid has an integer value vi, j. Find the path of higher cost starting from any position of the first line, to any position on the last row of the grid. Suppose that the The cost of the path is the sum of the values of the cells way to go. However, from a cell x, j, a next cell of the path must be one of three options: immediately below the left diagonal xi + 1, j-1, so immediately below xi + 1, j or an immediately below in diagonal right xi + 1, j + 1.

The optimal solution is 10: x1,2 -> x2,3 -> x3,3 -> x4.4

2244 1411 3222 1301