<img height="1" width="1" src="https://www.facebook.com/tr?id=1076094119157733&amp;ev=PageView &amp;noscript=1">

Solving Dynamic Programming problems using Functional Programming (Part 1)

Posted by Miguel Vilá on Mon, Sep 11, 2017

Dynamic programming (DP) is a technique used to solve innately inefficient recursive problems by storing solutions to pre-computed subproblems. The idea is to break a problem into smaller subproblems and save the result of each subproblem so that it is only calculated once. Dynamic programming involves two parts: restating the problem in terms of overlapping subproblems and saving the solution of the subproblems so that we can build the solution to the bigger problem.

 Overlapping subproblems are subproblems that may have the same dependencies. DP helps us here because we want to compute these common dependencies just once. There are two usual approaches:

  • The top-down approach starts trying to solve the bigger problem and uses memoization.
  • The bottom-up approach starts with the subproblems to build up the solution to the bigger problem and uses some data structure to save the subproblems solutions.

If you want to learn more about dynamic programming you can look into some of the links at the end of this post.

In my opinion the best way to understand Dynamic Programming is by looking at multiple examples. The first usual example is the Fibonacci sequence but I think that’s a bad instance of the general idea because nobody would call Dynamic Programming the “technique” of storing the two last solutions in two variables. But in more complex examples you will be able to see the “pattern”.

This post is not so much an introduction to DP. As you will see it’s more about how to implement DP algorithms in a functional way when taking the bottom-up approach.

The imperative perspective

Dynamic programming problems, when solved in a bottom-up fashion, usually rely in some mutable data structure which holds the solutions for smaller subproblems. For example let’s explore the 0/1 knapsack problem. This and this are good videos about it and describe a solution. Here’s my summary of the problem:

Given n items indexed 1, 2, ⋯, n with values dp-fp-v_i.gif and weights dp-fp-wi.gif find a subset of them with maximum total value that doesn’t exceed the input weight dp-fp-W.gif. Each item may be included just once.

For example, for this list of items with their respective value:

dp-fp-1.png

and maximum target weight W=9.

You can select the items 3, 4 and 5 for a total weight of 9 and a total value of 15. This is good but you could do even better by selecting items 1, 2, 4 and 5. In this case we would get a total value of 16 which is in fact the maximum you can get without exceeding the maximum weight of 9.

To solve this problem in the general case we can first break it by considering subsets. Let's start with a definition that allows us to express subsets of the problem:

dp-fp-2.png

For each item we have two choices: either we include it and gain it's value but we have reduced our available weight. Or, on the other hand, we ignore it and never use it. These two possibilities totally exclude each other so if we compute the maximum between them for every item (and for every possible maximum weight <= dp-fp-W.gif) then we can get the overall maximum. And these two possibilities correspond to two subproblem definitions.

The recursive formula that express is this:

dp-fp-3.png

According to this formula we can see that the problem dp-fp-4.png depends on two subproblems: dp-fp-5.png and dp-fp-6.png .

Here's a diagram that describes the subproblem dependencies:

dp-fp-7.png

The blue square represents a subproblem we are trying to solve. It depends on two other subproblems (the ones pointed by the arrows). And the final answer is the red square at the lower-right corner (the value dp-fp-9.gif). It represents the solution when we consider all the elements and with the problem's input weight. We can also see the "base" cases here: when considering no item the maximum value we can produce is and the same happens when the maximum weight is 0 (this assumes all dp-fp-wi.gif  > 0).

Drawing this kind of diagrams can be useful because it helps us to determine the shape of the iterations. In this case an element of a row depends on the values of the previous row. Thus we can build up solutions going down one row at a time.

A traditional imperative solution can be:

def knapsack(maxWeight: Int, value: Vector[Int], weight: Vector[Int]): Int = {
    val n = value.length
    val solutions: Array[Array[Int]] = Array.fill(n+1, maxWeight + 1)( 0 )
    (1 to n) foreach { i =>
        (1 to maxWeight) foreach { j =>
            solutions(i)(j) = if( j - weight(i-1) >= 0 ) {
                Math.max( 
                    solutions(i-1)(j) , 
                    solutions(i-1)(j - weight(i-1)) + value(i-1) 
                )
            } else {
                solutions(i-1)(j)
            }
        }
    } 
    solutions(n)(maxWeight)
}

This iterates one row at a time and computes the solution given the recursive formula. The time complexity of this is dp-fp-OnW.gif where dp-fp-n.gif  is the number of items to consider and dp-fp-W.gif  is the maximum weight. And the space complexity is also dp-fp-OnW.gif.

The previous solution can be improved given that we only need to remember the last row of solutions for each iteration:

def knapsack(maxWeight: Int, value: Vector[Int], weight: Vector[Int]): Int = {
    val n = value.length
    var solutions: Array[Int] = Array.fill(maxWeight + 1)( 0 )
    (1 to n) foreach { i =>
        val newSolutions = Array.fill(maxWeight + 1)( 0 )
        (1 to maxWeight) foreach { j =>
            newSolutions(j) = if( j - weight(i-1) >= 0 ) {
                Math.max( 
                    solutions(j) , 
                    solutions(j - weight(i-1)) + value(i-1) 
                )
            } else {
                solutions(j)
            }
        }
        solutions = newSolutions
    } 
    solutions(maxWeight)
}

 The space complexity of this will be dp-fp-OW.gif.

How to do the same thing functionally?

How could we do the same thing functionally? One of the main objectives in functional programming is avoiding side-effects. The most prominent side-effect that we have here is the mutation of a data structure and this can be avoided with immutable data structures.

But before doing that we should ask ourselves: is it worth it? Should someone calling the function knapsack care if it is implemented using mutable variables? My opinion is that no: it doesn't matter if knapsack is implemented with or without mutability even from a functional programming point of view. Let me explain.

This is because the implementation of knapsack that I listed before is already "purely functional" with respect to observable mutations! Will it return the same results when called with the same arguments whether it is implemented with mutable or immutable data structures? Yes! Is it implemented with any side-effect? Well, it has a mutable variable but does that mutable variable escape the function definition? No. Is it a global variable whose mutation can be observed from the outside? No. Thus, with respect to "observable mutations", the function knapsack is referentially transparent.

Having said that the motivation behind implementing knapsack functionally is just an exercise on how we can model this problem in a functional fashion. The idea is just to stretch our "functional" muscles: to see how far the paradigm can take us in an apparently mutable domain. But my opinion is that, even when following the functional programming ideas, mutation is not bad as long as it's just an implementation detail and not something that can be observed by the bigger system.

What we have seen so far

In this post we saw how to solve a common dynamic programming problem using an imperative approach. This involved mutation and a for loop. In the next post we will see an initial approach on how to do the same thing functionally.

Additional resources

If you want to know more about dynamic programming here are some good resources:

Posts by Topic

see all

Subscribe to Email Updates