While we have seen cases where greedy algorithms can work, there are cases such that no greedy algorithm will work for a problem. Divide and conquer is another approach that we can use, but it is difficult to get from a problem with an exponential brute force solution to one with polynomial time. Dynamic programming involves dividing a problem into smaller and smaller subproblems, and then “building up” these solutions for larger subproblems until we get back to the original problem. Because we do not look at every possible solution, our dynamic programming solutions should perform better than their brute force counterparts.

Readability: 9/10

The weighted interval scheduling problem can be defined as follows: given a single resource and intervals with certain weights that would like to be scheduled on that resource, can we find a solution that optimizes the total weight while also having zero overlaps? To solve this problem, we assume we have the intervals ordered by increasing finish time. When considering an optimal solution to this problem, we know that such an optimal solution either contains the last interval or it does not. If it does not, then the optimal solution is simply the optimal solution of all other intervals. We use recursion to write this algorithm, but discover that we will be recomputing the “opt” for the same interval many times. To solve this, we store each optimal solution for an interval in a memoized array so that we do not need to recompute things. This gives us O(n) efficiency assuming the intervals come presorted. The best way to find the actual intervals then, is not by keeping track as we go through the algorithm, but by going through our memoized array after we are done. This is also O(n) efficiency.

Readability: 7/10