Dynamic Programming C++ base classes
Over the last few months I’ve been exploring various dynamic programming (DP) algorithms, trying to get a feel for how to choose suitable sub-problems and the dimensions of those sub-problems, and when a top-down or bottom-up strategy is best. In principle, dynamic programming lets you break a problem down into suitable sub-problems, as long as they obey the “principle of optimality“, meaning you can use some broad state (result) of the sub-problem calculation, without needing the actual specifics of each solution.
I’ve also been playing lots with variadic templates in modern C++.
My little murrayc-dp-algorithms project is the result. It has base classes for both bottom-up DP and top-down DP and several examples that use them. The end result is only slightly useful, and is currently far from optimal for performance. But I still think it’s an interesting exercise that shows how these various DP algorithms really relate to each other. It should also explain how I came up with those examples in my earlier blog post.
Top-Down DP
Let’s start with top-down dynamic-programming, because it’s generally simpler. Calculating Fibonacci numbers is the classic example. This is clearly inefficient because every recursive call recalculates almost the same lesser Fibonacci numbers, twice. This is exponential, with time complexity of roughly O(2^n).
int f(int i) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
return f(i - 1) + f(i -2);
}
One simple way to avoid the wasteful recalculation is to cache the results and reuse them. That’s generally called Memoization. For Fibonacci number calculation, this is still not the best way, but it’s a useful example.
DpTopDownBase provides a framework for dynamic programming with memoization. You provide a calc_subproblem() implementation, which should use get_subproblem(). That get_subproblem() will return a previously-calculated result if it exists, or recursively call calc_subproblem().
1-Dimensional Top-Down DP
For instance, the top-down DpFibonacci class is declared like so, deriving from DpTopDownBase:
class DpFibonacci
: public murraycdp::DpTopDownBase< unsigned long, // subproblem type unsigned int // i > {
public:
explicit DpFibonacci(unsigned int n)
: n_(n) {}
This specifies that its calc_subproblem() (and the base class’ get_subproblem())will take an unsigned int and return an unsigned long:
unsigned long
calc_subproblem(
type_base::type_level level,
unsigned int i) const override {
// Base cases:
if (i == 0) {
return 0;
} else if (i == 1) {
return 1;
}
return get_subproblem(level, i - 1)
+ get_subproblem(level, i - 2);
}
The level parameter is just for optional debug output, to show how deep we are in the recursive call stack.
It also implements get_goal_cell() so that the base class knows which value of n to use to get the result f(n). This just returns the n provided to DpFibonacci’s constructor.
We can then instantiate the class and call calc():
DpFibonacci dp(n); auto result = dp.calc();
The base DpTopDownBase::calc() method calls get_goal_cell() and calls calc_subproblem() for that cell. Because our calc_subproblem() implementation uses get_subproblem(), it will automatically avoid recalculating already-calculated sub-problems.
That DpTopDownBase::calc() method is a fairly simple example of the usefulness of C++ variadic template parameters to call one variadic method with the result of another variadic method, using tuples and std::experimental::apply(). And it’s type-safe at compile time all the way.
2-Dimensional Top-Down DP
But DpTopDownBase isn’t just good for a 1-dimensional cache, based on one parameter. The wonder of C++ variadic templates lets us specify multiple parameters for calc_subproblem and get_goal_cell(). Those overridden methods take just the right parameter types and just the right number of parameters.
And this is where top-down DP can be useful, because it might not be necessary to calculate all possible sub-problems for all possible values of these parameters.
For instance, in the Knapsack Problem, we have a knapsack with a certain maximum weight capacity, and we have several items of various weights and values. We want to find the set of items to put in the knapsack that maximises the value. We give each item an index number.
In the classic Knapsack DP algorithm, we then have 2 dimensions (or parameters) for each sub-problem: A count of items and a maximum weight. So if we have 5 items and total capacity of 100Kg, we can calculate the max value, f(5, 100Kg) by using other sub-problems such as f(4, 80Kg) along the way. It’s not likely that we’ll need to calculate all 5 * 100 possible subproblems, though it is likely that we’ll reuse some sub-problem calculations.
For instance, the top-down DpKnapsack class derives from the base DpTopDownBase like so:
class DpKnapsack
: public murraycdp::DpTopDownBase<
SubSolution,
SubSolution::type_vec_items::size_type,
Item::type_weight
> {
Again it overrides calc_subproblem() and overrides get_goal_cell(). This time it takes 2 parameters instead of just i:
SubSolution
calc_subproblem(
type_level level,
type_size items_count,
type_weight weight_capacity) const override {
And it can call get_subproblem() with those 2 parameters, letting the base class worry about how to cache the sub-problems and when to recalculate them. (This currently uses a rather inefficient generic hashing function for std::tuple<>s. )
Notice that we return a custom SubSolution class for the sub-problem result instead of just a number. This lets us store both the maximum value for that sub-problem and the items used in that sub-problem solution. That helps us to reconstruct the complete set of items for the sub-solutions along the way. However, that is inefficient because we won’t need all sub-solution item sets . It should instead be possible to write some generic code to reconstruct the solution by working backwards from the result of the goal. I’ll try that out sometime.
Again we can just instantiate the class and call calc():
//Items with their values and weights:
DpKnapsack::type_vec_items items{
{13, 15}, {12, 14}, {2, 13}, {10, 12},
{1, 11}, {7, 10}, {6, 9}, {5, 8},
{11, 7}, {14, 6}, {9, 5}, {4, 4}, {3, 3},
{22, 2}, {8, 1}};
DpKnapsack::type_value weight_capacity = 45;
DpKnapsack dp(items, weight_capacity);
const auto result = dp.calc();
std::cout << "solution: value: " << result.value << std::endl
<< "with items: ";
print_vec(result.solution);
std::cout << std::endl;
The top-down DpContextFreeGrammarParser , top-down DpMakeChange , top-down DpEditDistance , top-down DpParenthesization do much the same thing. The top-down DpTsp uses 3 dimensions and overrides calc() to choose the minimum result over all the sub-problems at the top level instead of just letting the default base calc() use the result of one goal sub-problem as the overall result.
I think it’s nice to separate the real heart of each DP algorithm from the code that does the boring caching and checking.
Bottom-Up DP
In bottom-up DP, we calculate every single possible sub-problem result, starting from our base case. Even if we won’t need every single possible result, this is often more efficient because we sometimes know when we can discard whole sets of sub-problems. For instance, looking again at the classic Fibonacci Numbers example, we only really need the last 2 sub-problem results:
int f(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
int result = 0;
int prev1 = 1; // f(1) = 0;
int prev2 = 0; // f(0) = 0;
for (int i = 1; i < n; ++i) {
result = (prev1 + prev2);
prev2 = prev1;
prev1 = result;
}
return result;
}
So we don’t need to cache all i results along the way. For a multi-dimensional DP algorithm, that can save us a lot of space.
1-Dimensional Bottom-Up DP
The bottom-up DpFibonacci class derives from DpBottomUpBase, specifying:
- the number of sub-problems to keep along the way: 2 to keep f(n-1) and f(n-2).
- the type of each sub-problem’s (and the final) calculation result: long for the result of f(5), for instance.
- the type of the input: int for 5, for instance, in f(5).
class DpFibonacci
: public murraycdp::DpBottomUpBase<
2, // count of sub-problems to keep
unsigned long, // sub problem type
unsigned int // i
> {
DpFibonacci again overrides calc_subproblem() and get_goal_cell(), with exactly the same implementation as the top-down version.
The base class’ calc() method then just iterates from 0 to n, calling the virtual calc_subproblem() method and then returning the result for the goal cell, based on calling the virtual get_goal_cell() method.
DpBottomUpBase keeps just the right number of previously-calculated sub-problems, while reusing the discarded sub-problem storage, by using my (funky) circular_vector.
DpTripleStep is very similar, though it needs to keep the 4 previous sub-problems instead of 2, and of course it does a different calculation per sub-problem.
2-Dimensional Bottom-Up DP
The bottom-up DpKnapsack class is again much like the top-down DpKnapsack implementation, but it again specifies that it only needs the previous 2 sets of sub-problems.
class DpKnapsack
: public murraycdp::DpBottomUpBase<
2, // count of sub-problems to keep.
SubSolution,
SubSolution::type_vec_items::size_type,
Item::type_weight
> {
Where the bottom-up DpFibonacci passed one count to the base class’ constructor, the bottom-up DpKnapsack passes two, one for each calc_subproblem() parameter:
DpKnapsack(
const type_vec_items& items,
type_weight weight_capacity)
: DpBottomUpBase(
items.size() + 1,
weight_capacity + 1),
items_(items),
weight_capacity_(weight_capacity) {}
The base DpBottomUpBase class uses these constructor parameters as ends of ranges, assuming that each range starts at 0. It will then iterate over the first range, iterating over the second range each time, like a nested for loop:
for (int items_count = 0; items_count < MAX_ITEMS; ++items_count) {
for (int weight_capacity = 0; weight_capacity < MAX_WEIGHT_CAPACITY; ++ weight_capacity) {
...
}
There is no way in C++ to nest an arbitrary number of for loops. But we can use variadic templates to declare an arbitrarily-nested vector. And thanks to my funky variadic templates for vectors of vector (of vectors of vectors, etc), the base class can generically call calc_subproblem() as if it had nested for loops, regardless of how much nesting there should be. My for_vector_of_vectors() takes the (nested) vector, and a series of start and end parameters for each level and eventually uses std::experimental::apply() to call the functor (a lambda, in this case) for each combination. To get that series of start and end parameters, it uses my funky tuple_interlace() to alternate starts (0) with ends.
The bottom-up DpEditDistance and bottom-up DpSubstringMatching do much the same thing.
Problems with DpBottomUpBase
The bottom-up base class has some serious limitations:
It only lets us discard older sub-problems in the first dimension, such as the Knapsack sub-problems for items less than n-2. But you might understand enough about your algorithm to know other sets of sub-problems that can be discarded at various times, based on less simple criteria. This would make the best use of space while avoiding recalculation. Maybe some recalculation would be OK as long as you could minimize it.
Also, it is limited to a simple iteration, using a range from start to end, using a simple operator++ to move to the next iteration. But sometimes you want to do something a little more complicated than an iterating for loop. For instance, my top-down DpTsp class finds a solution for the Travelling Salesman Problem by manipulating sub-sets in its calc_subproblem(). I could use gosper’s hack to create a suitable n-choose-k subset iterator, but it still needs to iterate over a further set of subsets missing each item from the parent subset, and I suppose that would be doable with another custom iterator. But the start and end iterators at each level would then have to be instantiated based on the values of the parent level, and cannot just be supplied before the whole calc() starts. Maybe I could do something with lambda functions to let these iterators be instantiated along the way.