Dynamic Programming Revisit

The core of dynamic programming: recursion with memorization. Breaking a big problem into small sub-problems and only computing each sub-problem once.

Notice dynamic programming is an algorithm that will essentially search the entire solution space

It’s usually helpful to think what’s the last step in your solution (top-down) and what sub-problem will it generate. But when it comes to building the solution, we usually prefer doing it bottom-up. This will be discussed more in later examples.

Weighed Interval Scheduling

Problem statement: Given an array of tasks containing start time, end time, and weight, Arr = [(s_1, e_1, v_1) … (s_n, e_n, v_n)]. Find a valid schedule that maximax the value. Notice a valid schedule refers that for any task i and task j in a schedule, task i and task j are not overlapping.

When it comes to intervals, a common technique is to sort all intervals by their ending time. This is pretty much the same as in the non-weighed interval scheduling, a special case that can be solved by using the greedy algorithm.

After sorting all intervals by their end time, it’s easy to find out for any task i, what are all the tasks that don’t overlap with it? Just do a binary search to find the last task j that finishes before task i start, i.e. f_j <= s_i. And all tasks from index 0 to j, inclusive, are not overlapping with task i. We can sort the original task array and find out the last non-overlapping index for each task, p(i), in O(n*lg(n)) time.

Then, just consider the last interval in our sorted array. Do we take it or not? What are the subproblems?

Say OPT(i) means the maximum value we can get in intervals 0 to i, inclusive. Then just consider the last interval in our sorted interval array. There are only two cases:

1. if we take it, we gain a value of v_i, but we lose the oppotunity to take all intervals from p(i) + 1 to i – 1. The sub-problem problem becomes what is the maximum value we can get from intervals 0 to p(i), i.e. OPT(p(i))
2. if we drop task i, the sub-problem becomes what is the maximum value we can get from interval 0 to i – 1

Thus, the recurrence formula is

OPT(i) = Max(OPT(p(i)) + v_i, OPT(i-1))

The base case is simply is we have no intervals left, OPT(-1) = 0

When it comes to building the function, we can start computing the value of OPT(0) and then OPT(1), …

The total time complexity for this recurrence is just O(n) since we are looping n times and in each interaction, the time used is only O(1)

Thus the total time complexity is O(n * lg(n)) and space O(n)

0/1 Knapsack

Problem statement: given an array of items, each item has a weight and value, Arr = [(w_1, v_1) … (w_n, v_n)], and given a total weight constrain W. What is the maximum value we can get such that the total weight is less than W.

This is pretty much the same as the previous problem.

Consider the last item i, there are only two cases:

1. If we take it, we gain a value of v_i but use part of the weight constrain, w_i, the subproblem is what are the maximum value we can get in item index from 0 to i-1 under the updated constrain W – w_i
2. If we drop it, the subproblem is simply finding the maximum value in item index from 0 to i-1 under the original constrain W

Thus, we can define OPT(i,W): the maximum value in items index from 0 to i under the constrain W, and our recurrence formula is

OPT(i, W) = Max(OPT(i-1, W-w_i) + v_i, OPT(i-1, W))

The base case is either if we run out of W, i.e. W = 0, or we don’t have any items left, i.e. i = -1. In such cases, the maximum value is just 0

Overall time complexity O(W*n)

Notice this is not an efficient solution since the time complexity is has a polynomial of an input value W. We call such algorithm has pseudo-polynomial time complexity.

Sequence Alignment

Problem statement: Given two strings, str1 and str2. What is the minimum number of operations(add, revise and delete) we need to make these two strings identical?

The idea is similar, consider the last char in str1, i.e. str1[i], and the last char in str2, i.e. str2[j]. What are the possible cases and subproblems?

1. If str1[i] == str2[j], we don’t need to perform any operation and we just need to find out what is the number of operations needed to align str1[:i-1] and str2[:j-1]. This seems like a subproblem that can be solved recursively.
2. If str1[i] != str2[j], we can a)add an char to str1, b) add an char to str2 to make them look the same or c) revise str1[i] or str2[j]. So the subproblem in the case a is what is the # of operation needed to align str1[:i] and str2[:j-1], in case b) # of operation needed to align str1[:i-1] and str2[:j], in case c) # of operation needed to align str1[:i-1] and str2[:j-1]

Define OPT(i,j): # of operation needed to align str1[:i] and str2[:j]

Recurrence formula:
OPT(i,j) = Min(OPT(i-1, j-1) if match else OPT(i-1, j-1) + 1, OPT(i-1, j) + 1, OPT(i, j-1) + 1)

Base case is either i == -1, OPT(-1, j) = j + 1 or j == -1, OPT(i, -1) = i + 1

We can see that OPT(i,j) depends on OPT(i-1, j), OPT(i, j-1), and OPT(i-1, j-1). We can fill the table either row-wise or column-wise. And row i/colon j only depends on row i-1/colon j-1

Time complexity: O(mn), Space(m)

Notice if one needs to reconstruct the operations of getting the minimum number of operations, the space is no longer linear. To achieve a linear space while having the same time complexity, we can add divide and conquer on top of this dynamic programming approach. This might be covered later in a separate post.

Bellman-Ford: Finding the minimum distance in graph with negative weight

Problem statement: consider a graph G=(V, E) where some e in E can be negative. What is the shortest distance from node s to t?

First, notice that if there are any negative cycles in any path from s to t, the minimum distance is just -inf, since one can go into the cycles as many times as he wants and the distance will always become smaller. Actually, Bellman-Ford is able to detect if there are any negative cycles in the graph.

Let’s just assume there aren’t any negative cycles for now. The tricky/underlying condition of this problem is in any path that has the minimum distance, the total edges in that path are always less than |V|-1.

The above holds because if a path contains more than |V|-1 edges, it must contain a cycle. Since we assume that there are any negative cycles in the graph, that cycle must have a positive weight and one can always remove such a cycle to get a smaller s-t distance.

Then, a natural question comes out: Does the minimum cost path actually need |V| – 1 edges?

1. If it does need, consider the all the nodes W = {w_1, … w_k} s.t (w_i,t) in E, i.e. all nodes has a edge to destination t. Any s-t path must go through at least one node in W. Since such (w_i, t) uses one edge, the subproblem become what’s the minimum cost path from s to w_i with |V|-2 edges
2. If it doesn’t, the subproblem is actually finding the minimum cost path form s to t with |V| – 2 edges

Define OPT(i, v): the minimum cost path from s to v using at most i edges

Recurrence formula
OPT(i, v) = MIN(OPT(i-1,v), OPT(i-1, w_i) + cost_vw_i) for all w_i s.t. (w_i, v) in E)

The base case is a) if we run out of edges, i.e., i == 0, OPT(0, v) = INF. Or b) v == s, cost is 0 since no edge is need.

Time complexity: O(|V| * |E|). Notice for all nodes, we only need to consider all its neighbors and this is bounded by O(|E|).

We can also improve the space complexity to O(|V|). This might be discussed in a separate post.

Finding negative cycles in the graph is based on whether the minimum cost continuously decreases. We can perform another iteration to find the min-cost s-t path by using |V| edges. If we find out the min-cost path using |V| – 1 is greater than the one using |V| edges. This means we have a negative cycle in the graph. As for picking node s and node t, we can make up two new nodes s and t connecting with all nodes in the graph. And run Bellman-Ford with an extra iteration.

Summary

So far we have revisited a few classic dynamic programming problems. To solve these problems, it is usually helpful to think of the recurrence formula top-down and build a solution bottom-up. Again, the key of dynamic programming is recurrence and memorization. Identify the sub-problem that can be solved recurrently and come up with a recurrence formula. When explaining a dynamic programming algorithm, it’s usually helpful to make the meaning of each entry and the relationship between entries clear.

It’s very important that one understands the principle of an algorithm and its application instead of learning by rote, memorizing the pseudocode and complexity for single problems.

I might make mistakes in some of the places. Any comment or suggestions will be appreciated.