Dynamic Programming

Dynamic programming solves problem by combining the solutions to subproblems.

• DP applies when subproblems overlap- that ism when subproblems share sub sub problems.
• In this context, D&Q does more work than necessary.
• DP solves a subproblem only once and caches the partial result.
• DP is typically used in optimization problems.
• While developing a DP algorithm we follow 4 steps:
  1. characterize the structure of an optimal solution
  2. recursively define the value of an optimal solution
  3. compute the value of an optimal solution, typically following a bottom-up approach
  4. compute an optimal solution from previously computed solutions of smaller problems. DP problems can often be solved
• TOP-DOWN: Natural recursion but first check if we already solved a subproblem
• BOTTOM-UP: Sort subproblems by size and solve them in order using results from smaller problems to solve bigger ones. This approach has generally a smaller recursion footprint.

There are two key indicators that we should use DP:

• Presence of an optimal solution
• Overlapping subproblems (if we do not recursively revisit subproblems D&Q may be more appropriate)

Note that a problem exhibits optimal structure if an optimal solution contains within it optimal solutions to subproblems.

You will find yourself following a common pattern in discovering optimal sub-structures:

• Show that a solution consists of making a choice and that making this choice leaves one or more smaller subproblems.
• You suppose that for a given subproblem, you are given the choice that leads to an optimal solution.
• Given this choice, you characterize the resulting space of subproblems
• show that subproblems' solutions must themselves be optimal by using a "cut and paste" approach, i.e. trying to find a contradiction.

Note that subproblem must also be independent (i.e. not share resources)