This chapter is about dynamic programming, which is a more powerful approach than greedy or divide and conquer methods. The basic idea is kind of the opposite of greedy approach. You explore all possible solutions to a problem but breaking a problem up into subproblems, the building up the correct solution into larger subproblems. This may seem to be close to brute-force, but it is not because of the way it explores the possible solutions. It never explicitly looks at every solution, but carefully breaks it down so that we can find an optimal solution with a good running time.

This problem is an extension of the interval scheduling problem that we developed a greedy solution for previously. The difference is that each interval has a weight/value and we want to maximize the value of the accepted set of intervals. There is no greedy solution to this problem, but we can set it up similarly, with the n jobs ordered by finish time. For each job j, we define p(j) which is the largest interval that is compatible(i.e., disjoint) with j. To start considering our optimal solution, we know that job n is either in the optimal solution, or not in the optimal solution. If it is, then the optimal solution is now the value of n plus the opt(p(n)). If n is not in the optimal solution, then the optimal solution is opt(n-1). This intuitively develops into a recursive algorithm.

However, the running time is bad because the recursive calls lead to a lot of redundancy in computing the various optimal solutions. The fix to this problem is to use memoization, which is the process of storing the value of each optimal subproblem the first time we compute in and then just looking it up later. We can implement this process in O(n) time and then build up the set of intervals in the optimal solution from the array values of solutions for subproblems already computed. The algorithms are on pages 256-258. This process is confusing at first, but makes more sense as we go through it. It is actually pretty intuitive and very useful.