The two algorithmic design paradigms we've seen already are natural approaches to problems. Greedy algorithms operate on the idea of applying a single rule to making choices. Divide and conquer algorithms operate on the idea of dividing a problem into subproblems recursively and combining the results. But both of these approaches have weaknesses. Greedy strategies are often too simple for many problems, while divide and conquer algorithms may not be able to give meaningful improvements for problems with large solution spaces.
Our next algorithm design approach will seek to address these weaknesses. Dynamic programming is an approach first defined by Bellman in the 1950s. The apocryphal story behind the name suggests that Bellman wanted to make it sound more exciting to trick his superiors at RAND into thinking that this wasn't math. The programming part of the name is more instructive: it refers to planning (as it would have been used in the '50s) rather than our modern interpretation of coding.
Recall the interval scheduling problem:
The interval scheduling problem is: Given a list of $n$ jobs $j_1, j_2, \dots, j_n$, and each job $j_i$ has a start time $s(i)$ and a finish time $f(i)$, find the largest subset of mutually compatible jobs.
We will consider the weighted variant of this problem, where each job $j_i$ is also assigned a weight $w_i \gt 0$.
The weighted interval scheduling problem is: Given a list of $n$ jobs $j_1, j_2, \dots, j_n$, where each job $j_i$ has a start time $s(i)$, a finish time $f(i)$ and a weight $w(i)$, find the maximum weight subset of mutually compatible jobs.
Of course, here weight can be any metric you like: cash monies, importance, etc. In other words, we don't consider every job to be equally valuable and there are jobs that we would really like to get done more than others.
Consider the following instance.
The earliest finish time algorithm will choose the jobs on the bottom row, each of weight 1, which causes the job above, with weight 1000, to be blocked, since it is incompatible.
In fact, no greedy approach will work for this problem, so we need to think about how to come up with a different approach. First, it helps to fix the order of our jobs, so that they are in order of finish time, $f(1) \leq \cdots \leq f(n)$.
Something that helps in these kinds of problems is to think backwards. For instance, suppose we have an optimal solution. Which jobs are in the solution? Is the last job, with finish time $f(n)$ in our solution?
We will need some definitions.
Let $p(j)$ be the largest index $i \lt j$ such that job $i$ is compatible with job $j$. Let $\mathcal O_j$ be the subset of mutually compatible jobs chosen from jobs $1$ through $j$ with maximum weight, denoted $OPT(j)$.
What we want to compute is $OPT(n)$ by considering the possible subsets of maximum weight jobs on fewer jobs. Let's return to our question about the last job. If $n$ is in $\mathcal O_n$, then this means that it can't contain any jobs that aren't compatible with $n$. However, if $n$ isn't in $\mathcal O_n$, then we would have to ask the same question of job $n-1$.
Let's generalize this. Consider the following two possibilities for $j$ and $\mathcal O_j$.
These two observations give us the following equation \[OPT(j) = \begin{cases} 0 & \text{if $j=0$,} \\ \max\{OPT(j-1), w(j) + OPT(p(j))\} & \text{if $j \gt 0$.} \end{cases} \] This lends itself quite nicely to a recursive algorithm. Here, we assume that there is some bigger program that has already sorted the jobs and computed $p(j)$ and has it readily available.
\begin{algorithmic}
\PROCEDURE{computeopt}{$j$}
\IF{$j = 0$}
\RETURN{$0$}
\ELSE
\RETURN{$\max(w(j) + \mathtt{computeopt}(p(j)), \mathtt{computeopt}(j-1))$}
\ENDIF
\ENDPROCEDURE
\end{algorithmic}
This is a pretty simple algorithm that you can prove the correctness for using induction. Great! Except this algorithm has a worst case running time of $O(2^n)$. Wow, terrible!
So let's take a look at what's going on here. Consider the following instance.
Now, let's consider the following tree of calls that the algorithm makes in computing $OPT(n)$.
Note that when calculating $OPT(6)$ in this instance, we need to make a call to $OPT(5)$ and $OPT(4)$, which in turn make their own recursive calls. The result is a very large tree, which I've cut off for space purposes. However, the result is that we get something close to a full tree. Since each node is a recursive call, there is only a constant amount of work being done. However, recall that there are exponentially many such nodes, which means that we get something approaching $O(2^n)$.
However, it seems like there's a lot of repeated work going on here. Maybe we can take advantage of this. There are two main ways to do this.
The first is called memoization, which if you say out loud sounds like how you'd pronounce "uwu memorization". The idea behind memoization is that instead of recomputing each level of recursion, you simply store it once you've done it once, and future calls can look up the result rather than recompute it.
By giving access to a global array $M$ that stores the result of $OPT(j)$ in $M[j]$, we make an easy modification to our original algorithm to memoize it.
\begin{algorithmic}
\PROCEDURE{optmemo}{$j$}
\IF{$M[j] = \varnothing$}
\STATE $M[j] \gets \max(w(j) + \mathtt{optmemo}(p(j)), \mathtt{optmemo}(j-1))$
\ENDIF
\RETURN{$M[j]$}
\ENDPROCEDURE
\end{algorithmic}
How much better is this algorithm?
Algorithm 9.6 has worst-case running time $O(n)$.
There are one of two possible behaviours for a call to optmemo(j). Either it immediately returns $M[j]$ because it was already initialized, or it initializes $M[j]$ and makes two recursive calls. Therefore, we need to determine how many recursive calls this algorithm can make.
We observe that the calls are made only if $M[j]$ is not initialized and after $M[j]$ is initialized. The number of uninitialized entries of $M$ is 0 at the beginning of the algorithm and increases by one whenever recursive calls are made. This means there can only be at most $2n$ recursive calls, which gives a running time of $O(n)$.
This is much better, but so far we've only computed the weight of the best solution, but not the solution itself! Luckily, we can make use of the values $M$ that we've computed in order to find the corresponding solution. We make use of the fact that $j \in \mathcal O_j$ if and only if $w(j) + OPT(p(j)) \geq OPT(j-1)$.
\begin{algorithmic}
\PROCEDURE{findO}{$j$}
\IF{$j = 0$}
\RETURN{$\varnothing$}
\ELIF{$w(j) + M[p(j)] \geq M[j-1]$}
\RETURN{$\{j\} \cup \mathtt{findO}(p(j))$}
\ELSE
\RETURN{$\mathtt{findO}(j-1)$}
\ENDIF
\RETURN{$M[j]$}
\ENDPROCEDURE
\end{algorithmic}
We observe that most of the operations in this algorithm are basic operations, with the exception of the recursive calls. However, the recursive calls are bounded by $n$, since the calls are only made to values $i \lt j$. So Algorithm 9.8 has a worst-case running time of $O(n)$.
In total, the entire algorithm, including computing $OPT(n)$ and $\mathcal O_n$ runs in $O(n \log n)$ time, because of the requirement that our jobs are sorted in order of finish time.
Memoization was nice for augmenting the obvious but bad recursive algorithm that we came up with, but it is not really what we think of when we think of dynamic programming.
The key observation is that our initial view of the problem was top-down: we wanted to compute $OPT(n)$ and $OPT(n)$ was computed based on computing the subproblems $OPT(n-1)$ and $OPT(p(n))$. However, we can compute these subproblems from the other direction, bottom-up, starting from 0.
\begin{algorithmic}
\PROCEDURE{optiter}{$j$}
\STATE $M[0] \gets 0$
\FOR{$j$ from $1$ to $n$}
\STATE $M[j] \gets \max(w(j) + M[p(j)], M[j-1])$
\ENDFOR
\ENDPROCEDURE
\end{algorithmic}
We can prove this algorithm is correct by induction, similar to how we would for a recursive algorithm.
Algorithm 9.9 correctly computes $OPT(n)$.
We will prove that $M[n] = OPT(n)$ by induction on $n$. First, consider $n = 0$. Then $M[0] = 0 = OPT(0)$ by definition.
Now assume that $M[j] = OPT(j)$ for all $j \lt n$. By definition, we have \[OPT(n) = \max\{w(n) + OPT(p(n)), OPT(n-1)\}.\] By our inductive hypothesis, we have \[OPT(n) = \max\{w(n) + M[p(n)], M[n-1]\},\] and therefore $OPT(n) = M[n]$.
One thing to keep in mind when doing these proofs is to take care not to mix up $M[j]$ and $OPT(j)$. That is, the crux of the proof is to show that $M[j]$ is $OPT(j)$—we only substitute them once we make this assumption (via the inductive hypothesis). The proofs that we'll be doing later on will clearly denote the value of the solution we want by $OPT$, and involve showing that our program computes and stores this value as intended.
Algorithm 9.9 clearly runs in $O(n)$ time: it iterates through a loop $n$ times, with the work inside each iteration taking $O(1)$ time. The only other observation that is necessary is that each iteration only refers to computations that have already been performed in previous iterations.
The approach that we've used for this problem will be the same one that we'll deploy for other problems that we solve using dynamic programming. The most crucial step is to treat your problem as a recursive problem and to describe the solution to this problem recursively—i.e. as a recurrence.
In describing your problem as a recurrence, you identify the subproblems you need to solve. Once you have done this, it is a simple matter of storing the solutions these subproblems, which are the early values of your recurrence. Once you have done this, proving that your algorithm is correct is a matter of proving that the algorithm correctly stores the solutions to your recurrence.
The process is summarized as follows: