The basic idea of dynamic programming is the opposite of the greedy strategy: one implicitly explores the space of all possible solutions by carefully decomposing things into a series of subproblems, and then building up correct solutions to larger and larger subproblems.

Weighted Interval Scheduling

Each interval in the list will have a value(or weight) and we want to accept a set of intervals that has the maximum value.

The greedy solution of interval scheduling is just a special case when all the weights of the interval are equal to 1, and most of the greed algorithms will not solve this problem optimally.

Suppose that the requests are sorted in order of the finishing time. p(j) is defined as the largest index i < j that intervals i and j are disjoint.

Let O be the optimal solution, either interval n belongs to O, or it doesn't. If n belongs to O, no interval between p(n) and n belong to O.

Let Oj denotes the optimal solution of the form 1,2,...,j, and OPT(j) denotes the total weight of the solution. Since j could either belongs to O or not, $OPT(j) = max( OPT(p(j)) + v_j, OPT(j-1))$

def get_OPT(j):
	if j == 0:
		return 0
	return max(weight[j] + get_OPT(p(j)), # include the curr
						get_OPT(j-1) # doesn't include the curr
						)

This recursive approach would take exponential time to run in the worst case.

Memoizing the Recursion

It's easy to find out that there are a lot of redundancy when solving the subproblems cause by the recursion, like we might calculate the same j more than once. So one way to cut that is to do memoization.

cache = { 0:0 } 
def mem_get_OPT(j):
	if j in cache:
		return cache[j]
	cache[j] =  max(weight[j] + get_OPT(p(j)), # include the curr
									get_OPT(j-1) # doesn't include the curr
									)
	return cache[j]

The progress measure is the number of keys in cache. Initially the number is 1, and it will grow to n + 1, since there are total n+1 unique subproblems. The running time of mem_get_OPT is O()n if the intervals are sorted by their finishing time.

Find Solution

def find_solution(j):
	if j == 0:
		return []
	if valuep[j] + cache[p(j)] > cache[j-1]:
		return find_solution(p(j)) + [j]
	return find_solution(j-1)

Since the recursive call only on strictly smaller values, it makes a total of O(n) recursive calls. Therefore, the function returns an optimal solution of the problem in O(n).

Principles of DP

On the previous example, it's easy to see that the key to convert an exponential-runtime problem to a polynomial-runtime problem is the array(or hash-map) M. Once we have the array M, the problem is solved: M[n]contains the value of the optimal solution on the full instance, and Find-Solution can be used to trace back through M efficiently and return an optimal solution itself.

The point to realize is that, instead of using a recursive approach, we can directly compute the entries of M using an iterative approach. For instance, the previous problem can be changed to