This is an old revision of the document!
Table of Contents
Chapter 6: Dynamic Programming
Chapter 6 Front Matter and Section 6.1: Weighted Interval Scheduling, a Recursive Approach
The basic idea behind dynamic programming is similar to that of divide and conquer and opposite to that of greedy: dynamic programming divides the problem into subproblems and then takes the solutions to those to create the solution to the larger problem. This leads us to think that the dynamic programming approach may reach up to the brute force search time, however we will never actually need to examine every solution to our problem explicitly.
6.1 a Recursive Approach to Weighted Interval Scheduling
First, some notation to assist discussion. We will call p(j) the largest index i<j such that i and j are disjoint. This is to say that i is the leftmost interval that ends before j begins. We can also consider an optimal scheduling, the precise contents of which are unknown, that we will call O. We know that no interval between p(n) and n can be included in O if n is included in O because they overlap n. Additionally, O including n also includes an optimal solution for intervals {1,…,p(n)} because if it did not we could simply replace whatever solution was there with that optimal solution without fearing a loss of optimality or overlapping n.
Using that principle we can develop the statement that a an interval j should only be added to the solution if the sum of it and its optimal solution for p(j) is greater than the optimal solution of j-1. This statement obviously lends itself to recursion, since one must calculate the optimal set of intervals for p(j) and for j-1. Another thing that is easy to see from this includes the algorithm's possible invocation of redundant recursive calls.
The redundant recursive calling can be solved by memoization, which creates an array M that stores the results of the function's calling on j in case it is called on j again. The memoization array helps the algorithm to run in linear time instead of exponential. Somehow this also helps the algorithm to return to solution, in addition to its value, in linear time. I think it may take the solution with the optimal size from M and return that and the solution that it calculates but I can not tell for sure.
6.2 Principles of Dynamic Programming: Memoization or Iteration over Subproblems
The iterative version of the algorithm works by directly computing the entries in M rather than relying on the memoized recursion present in the recursive version. This algorithm works by iterating though the n items and computing each ones value, which is then stored directly in the array. It is easy to see that the algorithm then has linear running time since it will execute a constant time operation on each of its n passes through the loop.
From here we are able to develop an outline of dynamic programming. There are three properties that should be true of a problem in order to guide or development of a dynamic programming approach to solving the problem. First, there must be only a polynomial number of subproblems. Additionally, the solution to the original problem should be easy to arrive at from the solutions to the subproblems. Finally, there should be an ordering to the subproblems which allows the solution of some subproblems to be computed from the solutions of other subproblems.
Sometimes, it can be a challenge to determine whether it is more useful to first reason about the structure of the optimal solution or whether it is more useful to come up with subproblems that seem natural and then figuring a recurrence which links them. In this way, dynamic programming can be reminiscent of a chicken-and-the egg reasoning puzzle.
