Puzzle - nXn grid of +ve, -ve integers. Find optimal path through it

You have an NxN grid containing a set of positive and negative numbers, and you must find the optimal path through it. The path must pass through exactly one cell in eac开发者_如何学Ch row, and its cells on adjacent rows must be connected either vertically or diagonally. Can you find an algorithm for solving this problem without evaluating every permutation?

---

I'm assuming the "optimal path" is defined as the path with highest sum?

You can use dynamic programming. For each row, set the elements of that row to the optimal path value ending at that row. So

solution[i][j] = grid[i][j] + max(solution[i-1][j], solution[i-1][j-1], solution[i-1][j+1]) 

taking into account boundary conditions of course. The initial conditions would be:

solution[0][j] = grid[0][j]

You also need to keep track of the actual path taken (which grid elements are chosen) by the optimal path. Once you get to the last row, go through the row and find the maximum value. That will give you the optimal path as well as its value.