Coordinate DP

The optimal subproblem in this type of DP is usually the max/min value from the origin to the current location.

We can either define/solve by prefix or suffix.

The state is usually explicit given in the problem, array or grid and each element represents its own state.

Then we just have to use tabulation to build the graph implicit in an easy-to-code topological order.