In the previous post, we derived the closed form for the non-adjacent selection problem:
$$ F_{n, m} = {n - m + 1 \choose m} $$
Now we discuss how to implement this efficiently in Python—from a simple factorial-based solution to library implementations. For the common case of computing the answer modulo a large prime (e.g. in competitive programming), see the next post.
We can reflect the closed form in very trivial Python code:
In the post, we discuss the basics of Recursion, Dynamic Programming (DP), and Memoization. As an example, we take a combinatorial problem, which has very short and clear description. This allows us to focus on DP and memoization. Note that the topics are very popular in coding interviews. Hopefully, this article will help to somebody to prepare for such types of questions.
In the next posts, we consider more advanced topics, like The Art of Generating Functions and Cracking Multivariate Recursive Equations Using Generating Functions. The methods can be applied to the same combinatorial question. Let’s start from presenting the problem.