Dynamic programming

Dynamic programming, like divide and conquer, involves breaking a larger problem down into sub-problems recursively but instead of combining the results after recursion dynamic programming stores the solutions to sub-problems and these can later be used to solve other sub-problems or to obtain an optimal solution.

Dynamic programming algorithms covered:

• Weighted interval scheduling
• Subset sum
• Sequence alignment