The notion of generating functions and its application to solving recursive equations are very well-known. For reader who did not have a chance to get familiar with the topics, I recommend to take a look at very good book: Concrete Mathematics: A Foundation for Computer Science, by Ronald L. Graham, Donald E. Knuth, Oren Patashnik.
Generating functions are usually applied to single variable recursive equations. But actually, the technique may be extended to multivariate recursive equations, or even to a system of recursive equations.

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.

Powered by the Academic theme for Hugo.