Two Cents on Dynamic Programming

Mon Jul 24 23:48:00 2017 , 0x00019913

Of the elementary topics in computer science, I’ve found dynamic programming to be the most weirdly difficult to intuit to my satisfaction. So here’s a little compendium, in no particular order, of standard-ish problems with brief explanations and explicit recursions. I’ll use the symbol M to denote the optimal solution.

I won’t go into code nor write out how the top-down approach turns into bottom-up; it tends to be a comparatively easy conversion.

But First…

tl;dr: DP is hard.

The way to solve a dynamic programming problem seems to hinge, anticlimactically, on internalizing the thing everyone says to do: break the problem into smaller problems.

Often the reasoning will be of the form “let’s take an arbitrary subproblem and figure out the ways we could’ve arrived at that problem from some smaller subproblem” (e.g., the knapsack problem or the domino tiling problem) or, equivalently, “take a subproblem and enumerate the ways it could be reduced to a smaller subproblem”. The degrees of freedom in a problem are a determining factor: for instance, when finding the longest palindromic subsequence of a string, you have to match up pairs of characters and so end up closing in from both ends of the string; thus the optimum M is bivariate and the runtime ends up being .

Additionally, a repeating pattern (or perhaps even a defining feature) seems to be the task of finding a path through the problem that extremizes a quantity; this quantity is M. The result of the calculation will tell you the extremum but not the path, but you can trace it back by looking at the intermediate values of M.

In a sense, I won’t provide a justification for why dynamic programming is the right approach to a problem; I’ll just describe how you do it and leave it at that. It’s entirely up to the solver to recognize a dynamic programming problem as such.

0/1 Knapsack

We have an array of values and an array of corresponding weights . The knapsack’s weight capacity is and we’d like to pick items to put into the knapsack while maximizing the total value and not overfilling the knapsack.


The subproblems are the elements from to . Start with the full list of items cut it down item by item from the end, iterating from to and keeping track of how much capacity we have. M is the total value in the knapsack at a given point. Note that the optimum varies with and with capacity, so we’ll have a bivariate M.

Consider the th item, with value and weight , while the knapsack has units of capacity left. Two cases here:

  1. The item doesn’t fit (), so the value in the knapsack is the same as at the next step (item ).
  2. The item fits, so we can take it or not take it. If we take it, the value of M at this item is plus the M we get at item , but we’ll only have units of capacity to use with that item. If we don’t take , we just move on to with the same knapsack capacity. The value at is the max of these two possibilities.


Longest Palindromic Subsequence

Given a string of length , e.g., “AEDCFDEC”, find the length of the longest subsequence, not necessarily contiguous, that is a palindrome (LPS). Here it would be “EDCDE”.


We again start cutting elements off the edge, but this time we do it off both ends independently. Why? Hindsight. :P My intuition is that we end up zeroing in on both ends of the palindrome and the palindromes nested inside, so we need to vary both the start and end. (This means we again have a bivariate M.)

The subproblems are the substrings of , specifically . M is the length of the palindromic subsequence.

Start from the ends of a particular substring. Are the two endpoints equal ()? Then we might as well include those in whatever palindromic substring it contains, so M for this pair equals 2 plus the length of the substring excluding its two endpoints. Are the endpoints not equal? Then M is the length of the LPS of the same substring minus one of its endpoints (take the max of the two choices).


Longest Common Subsequence

Maybe the best-known DP problem.

Say we have two strings and , e.g., “AGCAT” and “GAC”. Find the length of the longest common subsequence (not necessarily contiguous within either string). Here the LCS is “GA” or “AC”.


Because we’re not comparing earlier and later elements as we did in the LPS problem, we can just have one iterator for each string. Let’s say the subproblems are the substrings up to character and of the two strings, respectively. M is still bivariate, though.

Say we have two substrings. Are the last characters equal ()? Then we might as well include those in the common substring. So M here is 1 plus whatever the LCS is of these two substrings excluding the endpoints. Are they different? Then we see what happens if we ignore either one of them, i.e., M is the max of the LCSes after ignoring one or the other.

The edge case is or , in which case M is because a substring of length can’t have an LCS with any other string.


Make a String into a Palindrome

What’s the smallest number of characters you have to add (not remove, mind) to string to make it a palindrome?


Once again, we’re comparing two elements of the string, so we need two iterators. Consider any substring from to . Are the first and last characters the same ()? Then we can just ignore them and move on to computing the result for the and . Are the endpoints different? We imagine that we add an element to either end to make the endpoints match, then cut those off and recurse on the substring that’s left. This means that M will be 1 (for the char we added) plus the min of M on and .


Number of Ways to Write a Number as a Sum

This one’s from Jaehyun Park’s notes. Calculate the number of ways in which you can write a number as a sum of , , and . Of course, and are the same sum.


This is a “how can we form a subproblem from smaller subproblems” example. Consider a number and think about how we could’ve arrived at it from a smaller number. Either we got there by adding 1 to , or by adding 3 to , or by adding 4 to . The number of ways we could’ve gotten to , then, is the numbers of ways we could’ve gotten plus the same for plus the same for .

You do, of course, have to hardcode M for .


Floyd-Warshall Algorithm

Say we have an undirected weighted graph with vertices labeled through , with the weight from vertex to vertex written as . (The weights are allowed to go negative as long as the graph doesn’t have negative cycles.) Find the shortest path between each pair of vertices.


As in the string problems above, we’ll consider the -to- path as a subproblem. However, we can’t just call it a day here because, given the best - path and a vertex outside the - path, there’s no way to check how to connect the vertex to the path. So this necessitates an additional iterator.

We formulate the objective like this: the shortest path from to using only vertices in the range (in addition to and ). So at , ’s shortest path to is just .

Then is the length of a path that goes from to through some subset of the vertices . What if we included vertex ? Then either the shortest -to- path doesn’t use or it goes from to to , so is the min of and the weight of the path through .


Traveling Salesman

Also from Jaehyun Park’s notes. Given a weighted graph of nodes numbered through with weights , find the shortest path that visits each node exactly once (AKA a Hamiltonian path).


Say we have a Hamiltonian path covering subset of the nodes and ending on node . This path has cost . The path got to node from some node , and the cost of the path till that point is . So, at node we just minimize over all .

Note that this is still quite exponential - the first argument of M varies with every single combination of the vertices. Still beats the naive solution, though.


Of course, because the graph consisting of has no cost.

Longest Increasing Subsequence

You have an array . Find the length of the longest increasing subsequence (LIS).


M is, as always, the objective - the length of the LIS ending on the term at index . Take the last term in the subarray. What’s the longest subsequence that ends with that term? It’s 1 plus the maximal for in the interval such that .


As stated, we do need to find every such that . This makes the algorithm . We can turn this into if we store predecessor information (see the Wikipedia article).


DP Examples

DP Lecture from CMU

Jaehyun Park’s lecture notes from Stanford

Floyd-Warshall algo on Wikipedia