In the two previous posts, we used open recursion to provide efficient solutions to dynamic programming problems, keeping the following aspects decoupled: The recurrence relation: the solution to our problem The memoization strategy: indexing into a vector The order in we compute the sub-solutions As a reminder, here is the open recurrence relation we based... Continue Reading →

In the previous post, we explored how we could leverage open recursion to solve a dynamic programming problem, while keeping the following aspect decoupled: The recurrence relation: the solution to our problem The memoization strategy: indexing into a vector The order in we compute the sub-solutions Today we will see how to apply this trick in... Continue Reading →

There is a large class of problems that we can solve by nice mathematical recurrence relations. The recurrence is usually simple to read, to reason about, and describes the solution with concision. But a naive translation of this recurrence into code will very often lead to a very inefficient algorithm. When the sub-problems of the... Continue Reading →