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

To whoever taking NUS's CS1101S that's currently reading this blog, the terms I use here are slightly different from the ones taught in the course. I will note below:

(The terms are not accurate, by the way, the definition of DP is different from memoization, for example.)

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: [code] 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)) [/code]

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 DP 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 recursion/DP 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 already smarter than most!

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 and DP much quicker.

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 come up with a DP solution, 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 $$$DP$$$ and 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" 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.

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: ```python

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 — 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.

Solution: (Remember to wrap in spoiler) python 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 recursion/DP 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: ```python

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) ```python

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): if lst is None: return None filter_tail = filter(lambda x: x != head(lst), tail(lst)) return pair(head(lst), remove_duplicates(filter_tail)) ```