3. Dynamic programming

Dynamic programming is regarded as one of the most difficult algorithm design techniques. Not only is learning dynamic programming difficult, but teaching it is also difficult. According to a seasoned computer science professor, “from my experience over decades, my conclusion is that it’s impossible to teach dynamic programming”.

One challenge in learning dynamic programming is that it is based on another difficult topic: recursion. If you have not mastered recursion, it can be very difficult to learn dynamic programming. Thus, learning recursion properly is possibly the first step in learning dynamic programming.

Another challenge is that the concept of dynamic programming is simple: divide the problem into subproblems and use a cache to solve subproblems efficiently. Because the concept is simple, it may not be useful to read a large amount of material to learn dynamic programming. Instead, a better approach may be to focus on a small number of problems and try to fully understand how dynamic programming works in those problems.

Despite the above, many people have learned dynamic programming.

Example problem

Let’s focus on the following problem: calculate the number of integer sequences that match a given pattern. The length of the sequence is \(n\), and each element is an integer between \(1\) and \(k\). The difference between any two consecutive elements in the sequence is at most one.

The pattern fixes some elements in the sequence, and you can freely choose the remaining elements, as long as the result is a valid sequence. Let’s use the value \(0\) to denote an element that is not fixed. For example, for the pattern \([2,0,3,0]\), there are \(6\) valid sequences:

• \([2,2,3,2]\)
• \([2,2,3,3]\)
• \([2,2,3,4]\)
• \([2,3,3,2]\)
• \([2,3,3,3]\)
• \([2,3,3,4]\)

The goal is to solve the problem in \(O(nk)\) time using dynamic programming.

Subproblems

The first step in dynamic programming is to define the subproblems. In this problem, a natural subproblem is to calculate the values of the function \(f(a,b)\): the number of valid prefixes of length \(a\) whose last element is \(b\).

If we can solve the subproblems, we can also solve the original problem because the answer to the problem is \(\sum_{i=1}^k f(n,i)\). This means that we iterate through all possible choices for the last element of the sequence.

Here are some function values for the example above:

• \(f(1,2)=1\), which corresponds to the prefix \([2]\)
• \(f(1,3)=0\) because the first element in the sequence must be \(2\)
• \(f(3,3)=2\), which corresponds to the prefixes \([2,2,3]\) and \([2,3,3]\)
• \(f(4,2)=2\), which corresponds to the prefixes \([2,2,3,2]\) and \([2,3,3,2]\)
• \(f(4,5)=0\) because no sequence ends with \(5\)

We can calculate the function values recursively:

• \(f(a,b)=f(a-1,b-1)+f(a-1,b)+f(a-1,b+1)\)

This means that the number of prefixes of length \(a\) that end with \(b\) equals the number of prefixes of length \(a-1\) that end with one of \(b-1\), \(b\) and \(b+1\).

A special case is \(a=1\), where the sequence consists of only one element. In this case the value of \(f(a,b)\) is \(1\) if \([b]\) is a valid prefix and \(0\) if \([b]\) is not a valid prefix.

In some cases, there are no valid prefixes:

• \(f(a,b)=0\) if \(b<1\) or \(b>k\) because each element must be an integer between \(1\) and \(k\)
• \(f(a,b)=0\) if the element at position \(a\) is fixed and is not \(b\)

Implementation

The second step in dynamic programming is to implement the solution. Here we can implement the solution as follows:

int calc(int a, int b) {
    if (b < 1 || b > k) return 0;
    if (pattern[a] != 0 && pattern[a] != b) return 0;
    if (a == 1) return 1;
    return calc(a-1, b-1) + calc(a-1, b) + calc(a-1, b+1);
}

This function works but it is not efficient because the function is called recursively a large number of times. However, we can fix the problem by using cache as follows:

int calc(int a, int b) {
    if (b < 1 || b > k) return 0;
    if (pattern[a] != 0 && pattern[a] != b) return 0;
    if (a == 1) return 1;
    if (dp_ready[a][b]) return dp_value[a][b];
    dp_ready[a][b] = true;
    dp_value[a][b] = calc(a-1, b-1) + calc(a-1, b) + calc(a-1, b+1);
    return dp_value[a][b];
}

Here we use two arrays that implement the cache:

• dp_ready tells us if we have alread calculated a function value
• dp_value contains the function values we have calculated

After this improvement, we have to calculate each function value only once, and then we can use the value stored in the cache. There are \(O(nk)\) different function calls, and each call works in \(O(1)\) time, so the solution works in \(O(nk)\) time.

Here is another implementation without recursion:

void calc() {
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= k; b++) {
            if (pattern[a] != 0 && pattern[a] != b) {
                dp_value[a][b] = 0;
            } else if (a == 1) {
                dp_value[a][b] = 1;
            } else {
                dp_value[a][b] = dp_value[a-1][b-1] +
                                 dp_value[a-1][b] +
                                 dp_value[a-1][b+1];
            }
        }
    }
}

Here we calculate the dynamic programming values using two loops. It is easy to see that this solution also works in \(O(nk)\) time.