Answer:
Every Dynamic Programming problem has a schema to be followed: Show that the problem can be broken down into optimal sub-problems. Recursively define the value of the solution by expressing it in terms of optimal solutions for smaller sub-problems. Compute the value of the optimal solution in bottom-up fashion.
