This page presents another DP problem with a step-by-step solution.

Problem Statement

You are a contestant in a new game show. Your goal is to determine if there is a sequence of binary mathematical operations that can transform a list of numbers into a final number. For example, given the numbers {7, 5, 4} and the goal 31, you can perform 7*5-4=31, so the answer is True. However, there is no combination with the list {1, 1} and the goal 999, so the answer for that case is False.

Rules are as follows:

  1. The operations are always read left to right, setting aside traditional order of operations. If you like, you can imagine nested parentheses like this: ((7 * 5) - 4) = 31.
  2. You have three operations to choose from: add, subtract, and multiply.
  3. Since the game show host wants you to be able to perform all of the math in your head, at no point will the number in sequence be greater than 1000 or less than -1000.
  4. There will be no more than 100 numbers in any particular sequence.


Step 1: Identify the States and Transitions.

This is often the hardest step, and it gets easier after you've solved more and more of these problems. It usually helps to draw it out on paper!

Let's take Operations as our example. It's rather obvious based on the problem statement that our three operations should be the transitions between states. This implies that the states should be the "running tally".

However, is the running tally sufficient for fully defining our states? For example, consider the input array [2,4,2]. The recursion tree for this case is going to look something like,

Operations recursion tree

where we started with a 2, the first operation is adding, subtracting, or multiplying the 4, and the second operation is doing the 2.

I notice something right away about this diagram: there is an "8" that you get by doing "2x4", but you also get "8" by doing "2+4+2". Something similar happens with 6. We need to differentiate those two states from one another, because we need to know where we are in the list of numbers.

The other thing I notice about this diagram is that there are two "-4"s, both at the same level. This is good: it's an example of a repeated subproblem.

By drawing this diagram, we were able to determine that the question consists of a well-defined, repeated subproblem. We can now move on to the next step.

Step 2: Implement Brute Force Recursion.

The next step is going to be writing a recursive function that passes the sample input. If you have a well-defined sub-problem, it shouldn't take very many lines of code. In Operations, pseudocode would be something along the lines of,

function recurse(running_tally, index):
    // Base Cases
    if index == NUMS.length: return running_tally == GOAL

    // Special case: restrict domain to -1000/1000
    if abs(running_tally) > 1000: return false

    // Recursive Step
    children = {
        recurse(running_tally + NUMS[index], index+1),
        recurse(running_tally - NUMS[index], index+1),
        recurse(running_tally * NUMS[index], index+1)
    return true iff any of children are true.

If you were to implement that pseudocode in a real language, you would pass the sample case. The algorithm will run in time O(3^N) since we have a branching factor of 3 and there are N levels of cases. Note that you should pass down "NUMS" and "GOAL" as constant arguments in your recursive function (I omitted them from the pseudocode for brevity).

Step 3: Optimize by Adding DP Cache.

Once you have your recursive function working properly, it's easy to slap on a cache. Refer to this post for examples on how you can add a cache to an existing recursive function.

In the end, you will have written a top-down DP solution to your problem that runs in time O(N*2001), which is exactly equivalent to the number of sub-problems (there are N elements in our list, and there are 2001 possible running tallies since we have the -1000/1000 bound).

Of course, there are many different ways to go about solving a DP problem. In the end, most solutions will end up solving the problem in roughly the same amount of running time. The top-down approach in this note is just the one that I find most intuitive.