Say there's a matrix with N rows and M columns.
You start the traversal at the bottom left, and your current points P is 0, and space S which is larger than 0. At each point in the matrix, the coordinate is either empty or contains points. If the points have size X and value V, you can choose to pick up the points or not when you reach a coordinate.
For traversing the matrix, we can only go up by one row and choose from one of the three columns (i.e. (i + 1, j − 1), (i + 1, j), or (i + 1, j + 1))
Picking up the points increases P by V and decreases S by X.
I'm trying to write a dynamic programming algorithm that would traverse this and return the best path resulting in the largest number of points.
I figure the subproblems are:
L(N, j) = Null
L(i, 0) = max(L(i + 1, 0), L(i + 1, 1))
L(i, j) = max(L(i + 1, j − 1), L(i + 1, j), L(i + 1, j + 1))
L(i, M) = max(L(i + 1, j - 1), L(i + 1, j))
Would that work? How would I go about introducing this to an algorithm?