Summary

This blog introduces a thinking model for beginners to help solve recursion and basic DP (recursion with memoization) problems. This kind of thinking, in my opinion, is one of the most important things beginners need to master in their programming journey (and for those taking CS1101S, it's like $$$50 \%$$$ of the problems in that course).

Notes

Some of the solutions below is very unoptimized. This is intentional as to not distract from the main point of the blog.

As the inspiration for this blog was from CS1101S, all the code in this blog will be written in Source (a subset of Python only used in CS1101S). Some of the examples also uses CS1101S definitions and functions as well. I will list them here for reference:

Disclaimer: This implementation is my own, it may differ from Source's implementation.

Implementation of relevant CS1101S built-in functions:

pair = lambda x, y: [x, y]
head = lambda p: p[0]
tail = lambda p: p[1]
#remove all elements that does not satisfy predicate p from xs
def filter(p, xs):
    if xs is None:
        return xs
    if p(head(xs)):
        return pair(head(xs), filter(p, tail(xs)))
    else:
        return filter(p, tail(xs))

Introduction

Taking the "learning how to code" course in NUS (CS1101S) has been a rather ... unique experience.

As a competitive programmer (CP-er), my intuition has developed enough that I can come up with basic recursive definitions and recursive solutions almost automatically. I think this also applies to most experienced CP-ers. For example:

• If a problem asks us to count the number of ways to partition an array into disjoint subarrays such that every subarray satisfies some condition, it seems intuitive to define $$$DP(i)$$$ as the number of ways to partition the first $$$i$$$ elements.

• If a problem asks us to choose the largest subset of an array such that it satisfies some condition, we may immediately define $$$DP(i,...)$$$ as the largest subset among the first $$$i$$$ elements, such that the subset has $$$...$$$

To us, these lines of thoughts seems natural and obvious, but for beginners? Not so much. In fact, I have seen many times when a recursive solution is shown in class, and my peers reacted with "How the heck are we supposed to come up with this?". And these people are NUS students! They are clearly capable students!

The classic (and surprisingly effective) way to fix this is, of course, through practice. With enough practice, one can probably pick up those patterns on their own (that's my experience, at least).

However, picking up patterns can only get you so far, and I think intuitively knowing how you might come up with a solution yourself is also important. Therefore, I have come up with a reasoning model that, in my opinion, can enable beginners to master recursion, memoization (and consequently DP) quicker.

Of course, you will still need to practice, this model can only help you make your practice more effective (and less frustrating).

Recursion

I am going to assume you already know what recursion is and basic use cases. If not, please refer to this page by YouKnowWho: Introduction to Recursion

There is a popular saying that goes along the line of "Before you try memoization/DP, you have to first come up with a recursive solution". Thus, in this section I will focus on how to come up with recursive solutions, ignoring Memoization for now.

For this, I am going to shamelessly steal introduce CS1101S's recursion model: The BWB model (wishful thinking). It stands for Base case, Wish, Bridge.

Basically, the idea is that your recursive solution can be seperated into $$$3$$$ main parts:

1. (Base case) We solve the problem for some trivial cases.

2. (Wish) We make a "wish" that we have solved smaller version(s) of our problem. In other words, we assume that we know the answer to those smaller version(s).

3. (Bridge) We create a "bridge" that connects our "wish(es)" to our original problem. In other words, we try to use the answers to smaller version(s) we "wished" for to solve the original problem.

Therefore, when deriving a recursive solution, we are going to fill in what our base case, wish, and bridge are going to be. Filling the base case is trivial (just solve by hand some small cases). What I personally do is figure out the wish and bridge first, then fill in the base case afterwards. The main difficulty lies in the other two parts. I shall present two ways of filling the Wish and the Bridge below.

Method 1: Guess the Bridge first, then see whether it connects to a Wish.

In summary, we are going to do a small "action" on our original problem, then see whether the problem reduces to a smaller version. If it does, then we make a "wish". Let's illustrate this with an example:

(Unbounded knapsack problem). Given a list of $$$n$$$ items numbered from $$$0$$$ to $$$n - 1$$$. Item $$$i$$$ has weight $$$W[i]$$$ and value $$$C[i]$$$. You are given a threshold $$$S$$$, you can choose any set of items, such that their total weight is $$$\leq S$$$. Find the maximum total value of the items you can obtain (out of all the ways you can choose). Note that you can choose an item any number of times. It is guranteed that $$$S, W[i], C[i] \geq 1$$$.

First of all, let's denote our recursive function. We denote max_value(W, C, S) as returning the maximum total value for the problem for the lists $$$W, C$$$ and the threshold $$$S$$$.

Okay, so what is our "bridge" here? Well, let's look at the definition above: a small "action" on our original problem. In this case, one natural "action" we can try is whether we take item $$$0$$$ or not. There are two cases:

1. We take the first item. In this case, our threshold will reduce to $$$S - W[0]$$$, and our list of items will stay the same. This is a smaller version of our problem, so we can make a "wish"! Of course, we will have to add the value of item $$$0$$$ back. Thus, the maximum value we can obtain in this case will be max_value(W, C, S - W[0]) + C[0]. Note that we need to check $$$S \geq W[0]$$$ for this case.

2. We don't take the first item. In this case, our threshold will stay the same, but our list of items doesn't! In particular, we can remove item $$$0$$$ from that list. So this is a smaller version of our problem! Thus, the maximum value for this case will be max_value(Wn, Cn, S). Wn, Cn are the new lists of weights and values after removing item $$$0$$$.

Therefore, we have our solution below:

# remove the first item out of the list
def remove_first(lst):
    new_lst = [None] * (len(lst) — 1)
    for i in range(1, len(lst)):
        new_lst[i — 1] = lst[i]
    return new_lst

def max_value(W, C, S):
    # base case
    if len(W) == 0:
        return 0
    Wn = remove_first(W)
    Cn = remove_first(C)
    if S < W[0]:
        #in this case, we cannot choose item 0.
        return max_value(Wn, Cn, S)
    else:
        return max(max_value(W, C, S &mdash; W[0]) + C[0],
                   max_value(Wn, Cn, S))

Exercise 1: A very natural "small action" that one might try is determining the first item that we take instead. This also solves the problem. You can try to figure it out yourself!

Solution:

def max_value(W, C, S):
    ans = 0
    for i in range(len(W)):
        #choose item i
        if S >= W[i]:
            ans = max(ans, max_value(W, C, S - W[i]) + C[i])
    return ans
    #Note that the base case here is implicit. The code above
    #will return 0 if we cannot pick any more items.

Method 2: Guess the Wish(es) first, then try to build the bridge

In summary, this is, in a sense, a reverse of the first method. We are going to first guess our "wish(es)" (smaller subproblems), and then try to use them to solve the original problem.

In my experience, for basic problems we mostly use the first method. However, this method can still come in handy at times, so it's still included. Let's illustrate this with an example:

(CS1101S Tutorial Question). Given a llist lst, write a recursive function remove_duplicates(lst) that removes all duplicates from lst. The order of the elements doesn't matter.

Okay, so how do we guess our "wish(es)" here? Sadly, unlike the first method, this method relies more on intuition and pattern recognition (ironic, given how this model is meant to help ease intuition/experience gaps).

For CS1101S students, there are two particular patterns that (I hope) they have internalized:

• For llist processing problems, the "wish" for a llist lst is usually tail(lst).
• For tree (CS1101S version) processing problems, the "wishes" for a tree tree are usually head(tree) and tail(tree). (for the CP version of tree, the "wishes" are usually the children subtrees of the original tree.)

Back to the problem, we can see that this is a list processing question, so we can use our pattern and guess that the wish is tail(lst). Now let's get to the bridge. Assume that we have ans = remove_duplicates(tail(lst)), what happens to ans when we add the first element head(lst)?

Well, ans may now have duplicates, of course. However, notice that the only duplicate it may have is head(lst). Thus, we can use our built-in function in Source filter to filter out all elements equal to head(lst) from ans, before adding head(lst) itself.

Therefore, we have our solution below:

#remove all elements that does not satisfy predicate p from xs
def filter(p, xs):
    if xs is None:
        return xs
    if p(head(xs)):
        return pair(head(xs), filter(p, tail(xs)))
    else:
        return filter(p, tail(xs))

def remove_duplicates(lst):
    #base case
    if lst is None:
        return None
    ans = remove_duplicates(tail(lst))
    ans = filter(lambda x: x != head(lst), ans)
    return pair(head(lst), ans)

Exercise 2: Actually, you can solve this problem by method $$$1$$$ too. Try it out for yourself!

Solution: (Remember to wrap in spoiler)

def filter(p, xs):
    if xs is None:
        return xs
    if p(head(xs)):
        return pair(head(xs), filter(p, tail(xs)))
    else:
        return filter(p, tail(xs))

def remove_duplicates(lst):
    if lst is None:
        return None
    filter_tail = filter(lambda x: x != head(lst), tail(lst))
    return pair(head(lst), remove_duplicates(filter_tail))

Memoization

I am going to assume you already know what memoization is. If not, please refer to this page by NUS: Introduction to Memoization.

Let us consider another problem:

Given a list of $$$n$$$ integers $$$a_0, a_1, \dotsc, a_{n - 1}$$$ and two numbers $$$l, r$$$. Count the number of ways to partition $$$a$$$ into non-empty subarrays such that the sum of elements in each subarray is in the range $$$[l, r]$$$. A subarray of $$$a$$$ is a sequence of continuous elements in $$$a$$$. For example, $$${ a_2, a_3, a_4 }$$$ is a subarray, but $$${ a_5, a_7 }$$$ is not. A partition of $$$a$$$ into subarrays can be understood as a way to "divide" $$$a$$$ into continuous blocks. For example, if we divide $$$a_1, a_2, a_3, a_4, a_5$$$ into $$$a_1 | a_2, a_3, a_ 4 | a_5$$$ then the corresponding partition is $$${{a_1},{a_2,a_3,a_4},{a_5}},$$$

Denote count_partition(a, l, r) as the number of ways to solve the problem above with list $$$a$$$, and constraint $$$[l, r]$$$.

Recursive solution

First of all, lets come up with a recursive solution. For this problem, we shall again use method $$$1$$$. One natural "small action" here is to consider what the last "block" is. There are $$$n$$$ possibilities, taking only $$$a_{n - 1}$$$, or $$$a_{n - 2}, a_{n - 1}$$$, or $$$a_{n - 3}, a_{n - 2}, a_{n - 1}$$$, and so on... That is so many different potential "wishes"!

However, don't let the large amount of "wishes" intimidate you. Let's consider one of those possibilities: Suppose that we assume the last "block" is $$$a_k, a_{k + 1}, \dotsc, a_{n - 1}$$$. Of course, we assume that the sum of the elements is in the range $$$[l, r]$$$ (checking is simple).

Then, our original problem will reduce to partitioning the remaining part of the array: $$$a_0, a_1, \dotsc, a_{k - 1}$$$. Thus, the number of ways for this case is count_partition([a[0], a[1], ..., a[k - 1]], l, r)

Notice that every valid partition falls into exactly one of those $$$n$$$ possibilities, so we will sum over all possibilities (making $$$n$$$ "wishes"). The solution is shown below:

#return new list containing the first k elements of lst
def get_first_k_elements(lst, k):
    ans = [None] * k
    for i in range(k):
        ans[i] = lst[i]
    return ans

def count_partition(a, l, r):
    def recur(lst):
        #base case
        if len(lst) == 0:
            return 1
        n = len(lst)
        ans = 0
        for k in range(0, n):
            #checking the sum of the elements 
            # lst[k] + lst[k + 1] + ... + lst[n - 1] is in [l, r]
            sum = 0
            for i in range(k, n):
                sum = sum + lst[i]
            if l <= sum and sum <= r:
                #lst[0] ... lst[k - 1] has k elements
                nxt_lst = get_first_k_elements(lst, k)
                ans = ans + recur(nxt_lst)
        return ans
    
    return recur(a)

Note that the recursive function here is recur, not count_partition. This is intentional: since l and r remain unchanged, we shall keep them outside recur to focus on optimizing one particular call to count_partition. This will also make the next part more convenient.

Adding memoization

One can notice how we actually call the recur with exactly the same argument many times. Thus, it's a good idea to try adding memoization.

Okay, so in order to add memoization, we will first need to detect when a function call (i.e function application) to recur has the exact same arguments as a previous call. The simplest way to do so is to keep a variable memo, which is a llist of all the arguments a that has been called so far. And then, each time we call we have to iterate through memo and then check whether two lists are equal...

Yeah. That is painful.

If you are not a CS1101S student and use normal Python/C++, then i guess you can use a dict or std::map, but then it will still be slow since you are comparing two lists...

Anyway, the point is: This solution is slow, and potentially painful. Fortunately for us, in this case there is a faster AND simpler way by using a "trick".

Change your representation!

Let's draw the recursion tree for a call to recur when $$$a=[1, 2, 3, 4], l = -10^9, r = 10^9$$$. It should look roughly like this:

Now, let's list all the distinct calls to recur: recur([]), recur([1]), recur([1, 2]), recur([1, 2, 3]), and recur([1, 2, 3, 4]). What do you notice?

You probably notice a few things like: There are only $$$5$$$ arguments, every distinct argument has a different length. But the crucial thing (hopefully you also noticed that) is that every argument is a prefix of the list $$$a=[1, 2, 3, 4]$$$.

(For those who don't know, a prefix of a list xs is a list b such that b can be created by taking the first $$$k$$$ elements of xs from the beginning)

You can try to draw the recursion tree for other arguments, too, and it will still hold! Why? This step can get a bit abstract, so bear with me here. Let's look at our old code again:

#lst[0] ... lst[k - 1] has k elements
nxt_lst = get_first_k_elements(lst, k)
ans = ans + recur(nxt_lst)

Notice how nxt_lst is simply a prefix of lst. Of course, one can notice how a prefix of nxt_lst is also a prefix of lst, and then a prefix of that is also a prefix of lst, ...

Therefore, every call to recur(lst) always satisfies the fact that lst is a prefix of the original list a by induction. Okay, so how does that benefit us? Well, ask yourself this: Do I really need to store the entire list? Perhaps, there is a way to store less things and still be able to "figure out" lst by using the original array a?

Yes! Notice how if you know that lst has length $$$k$$$, then you can immediately deduce that $$$lst={a_0, a_1, \dotsc, a_{k - 1}}$$$!. Thus, instead of having recur take in an entire list as an argument, simply having recur take in a single integer — the length of the list is enough!

With this, doing memoization becomes much simpler. We only need to compare two integers, and since the length of a prefix is at most len(a), we can just create two lists vis and memo of length len(a) + 1, where vis[i] tells us whether recur(i) has been computed, and memo[i] stores the result of recur(i). The solution follows:

def count_partition(a, l, r):
    #Note that k can go up to len(a), so len(memo) > k = len(a)
    memo = [-67] * (len(a) + 1)
    vis = [False] * (len(a) + 1)
    def recur(k):
        #base case
        if k == 0:
            return 1
        if vis[k]:
            return memo[k]
        ans = 0
        #the current prefix is a[0], a[1], ..., a[k - 1]
        for i in range(0, k):
            #gets the sum of a[i] + a[i + 1] + ... + a[k - 1]
            sum = 0
            for j in range(i, k):
                sum = sum + a[j]
            #checking the condition of sum in [l, r]
            if l <= sum and sum <= r:
                #a[0], a[1], ..., a[i - 1] has length i
                ans = ans + recur(i)
        vis[k] = True
        memo[k] = ans
        return ans
    
    return recur(len(a))

Note that your recursive function may not have a compact representation like this, depending on the problem. Sometimes you will have to use a more complex representation, or even store the entire list...

Exercise 3: What is the time complexity (i.e orders of growth) of the function count_partition above? Is there a way to optimize it so that it has orders of growth $$$O(n^2)$$$, where $$$n$$$ is the length of $$$a$$$? (For those who are curious, there exists an $$$O(n \log n)$$$ solution, but if you're still learning the basics of DP then don't worry about it :>).

def count_partition(a, l, r):
    memo = [-67] * (len(a) + 1)
    vis = [False] * (len(a) + 1)
    def recur(k):
        #base case
        if k == 0:
            return 1
        if vis[k]:
            return memo[k]
        ans = 0
        sum = 0
        for i in range(k - 1, -1, -1):
            #add a[i] into current sum
            sum = sum + a[i]
            if l <= sum and sum <= r:
                ans = ans + recur(i)
        vis[k] = True
        memo[k] = ans
        return ans
    
    return recur(len(a))

Exercise 4: Try to solve this problem: Given a list $$$a$$$ of $$$n$$$ integers. In each operation, you can choose two positions $$$(i, j)$$$ such that $$$i \lt j$$$ and $$$a_i = a_j$$$. After choosing the positions, create a new list $$$b = { a_{i + 1}, a_{i + 2}, ..., a_{j - 1} }$$$, then set $$$a = b$$$. What is the maximum number of operations you can perform?

def maximum_operations(a):
    if len(a) == 0:
        return 0
    memo = [[]] * len(a)
    vis = [[]] * len(a)
    for i in range(len(a)):
        memo[i] = [-67] * len(a)
        vis[i] = [False] * len(a)

    def recur(l, r):
        #[l, r] denotes subarray a[l], ..., a[r]
        if l >= r:
            return 0
        if vis[l][r] == True:
            return memo[l][r]
        ans = 0
        #You can just iterate through all possible pairs (i, j).
        #That's fine. But below is a bit of a harder and elegant 
        #solution for you to figure out :>.
        if a[l] == a[r]:
            #pair up (l, r)
            ans = max(ans, recur(l + 1, r - 1) + 1)
        #Note that unless we pair up (l, r), at least one
        #of l and r will NOT be paired up with anything.
        ans = max(ans, recur(l, r - 1))
        ans = max(ans, recur(l + 1, r))
        vis[l][r] = True
        memo[l][r] = ans
        return ans
    return recur(0, len(a) - 1)

Conclusion and Caveats

In conclusion, our thinking model goes roughly as follows: 1. Figure out the recursive solution to the problem. 1.1. Use the BWB model. Figure out what the "Bridge" and "Wish" are. 1.2. Two ways: Guess the "Bridge" by performing a "small action" on the problem, or guess the "Wish" by...trying things out. 2. Try to find a convenient/compact representation to your recursion arguments. 2.1 (Optional) Draw out the Recursion Tree for a small (but not too small!) case. 2.2 Ask yourself: Do you really need to store all these arguments in your recursive function? Is there a way to "store less" and still be able to figure out the necessary information? Can some properties you may have noticed from drawing the Recursion Tree help you here? 3. Perform memoization to avoid repeated subproblems.

Of course, in no way do I think this model is complete. That's why I posted it here, on Codeforces. If any of you guys notice some kind of hole in my model, or have a way to improve it, feel free to comment below. Worst case I will just ignore you (lol).

As an example, I will briefly present a weakness of this model: While it may create a working DP/memoization solution, that solution may be far from optimal. To illustrate this, consider a variant of our first problem:

($$$0/1$$$ knapsack problem). Given a list of $$$n$$$ items numbered from $$$0$$$ to $$$n - 1$$$. Item $$$i$$$ has weight $$$W[i]$$$ and value $$$C[i]$$$. You are given a threshold $$$S$$$, you can choose any set of items, such that their total weight is $$$\leq S$$$. Find the maximum total value of the items you can obtain (out of all the ways you can choose). Note that you can only choose an item once. It is guranteed that $$$S, W[i], C[i] \geq 1$$$.

There are two "Bridges" you can guess here, just like the first problem. - The first one is by considering $$$2$$$ possibilities: Take the first item or not take it. - The second one is by considering $$$n$$$ possibilities: Possibility $$$i$$$ is when the first item taken is item $$$i$$$.

Both solutions will use a function recur(w, c, s) where $$$w, c$$$ are the weights and the values of the items not chosen yet, and $$$s$$$ is the maximum threshold.

If you memoize the first bridge, then you will find out the property that at every call, $$$w, c$$$ are suffixes (reverse of prefixes) of the original respective lists $$$W, C$$$. This gives rise to a $$$O(nS)$$$ solution.

On the other hand, if you try to memoize the second bridge, then the only property that you can find is that $$$w, c$$$ are subsets of the original respective lists $$$W, C$$$. This helps a bit, but it still gives rise to an exponential time complexity (orders of growth).

Again, this is just a brief example, so I will not discuss the details here.

There isn't (to my knowledge) any kind of model to come up with the optimal DP/recursion/memoization algorithm. It is something that you simply gets better at over time.

Final note (1): I originally planned to introduce the art of Information Manipulation (it's not as intimidating as it sounds) to help figure out an "optimal" DP/recursive solution. This is what allows us to figure out the recursive/memoization solution for finding the shortest path in an unweighted graph. However, the above parts took wayyy more time than I expected, so we shall stop here. Perhaps I will make a part $$$2$$$ if I ever felt like it :>.

Final note(2): The exercises only has code solutions with minimal explaination. If you need a detailed solution, feel free to write a comment!