Dynamic Programming is the opposite of Greedy and is similar to divide and conquer. It is a good tool for problems which do not have greedy aspects and can only produce exponential divide and conquer solutions. Dynamic Programming is the process of decomposing all information into a collection of sub-problems and then using their solutions to solve progressively larger sub-problems. Overall, it is more powerful than the other strategies we have tried so far.

First, we will apply DP to the weighted interval scheduling problem. This is like the old scheduling problem except that now intervals can have differing values, rendering the old greedy algorithm(minimizing overlaps) obsolete. No other greedy algorithm is currently known. We will take a recursive approach although we could take an iterative approach if we chose. First, the book derives a complex equation representing a recurrence relationship. It simply means that we can find a solution by checking the final interval points vs the overlap points, applying and then recursing back to the next interval. Unfortunately, this algorithm is still exponential as it requires Fibonacci like computations. Luckily, this poor efficiency is caused by redundancy: making the same calls over and over again to re-find various sub-optimums. The solution is memoization: storing and then referencing the results of each of these calls with computer memory.