This is a Scheme translation of dynamic programming techniques from the book The Algorithm Design Manual-Springer (Steven S. Skiena, 2020). I was listening to an interview from Steven in a podcast and they mentioned that dynamic programming is a very hard thing to understand. I decided to give it a try and was surprised to see that it is nothing more than what in Lisp is known as tail recursion. Basically we store in a list (or an array) only the values calculated in the last iteration of a recursive function because that's all that we need to know the next values. This saves a ton of memory.
I begin with (fib-rec)and (fib-dp), i.e., recursive and "dynamic programming" implementation of the fibonacci series. I then move on to functions that calculate Pascal's Triangle (as and example that is given in Steven's book). Finally (pasc-better) is my optimization on top of it. It optimizes in three conditions:
- The first and last numbers in each "row" of Pascal's triangle is 1, so if k = 0 or k = n (the last number), the function returns 1 immediately.
- The second and second-to-last numbers are equal to the row's index (e. g.
(4, 1)and(4, 3)should return4), so ifk = 1ork = n - k, the function returnsnimmediately. - Lastly, and more importantly, Pascal's triangle is symmetric (e.g.
(10, 3)is equal to(10, 8). That means we only have to calculate half of it. We never have to calculatekfork * 2 > n. With this optimization we should have slightly more than double the speed. This is implemented in(pasc-better)
You can run and test this implementation at https://replit.com/@CaioFooBarros/DynamicProgramming. Since Scheme is a high-level language it's slower than C, for instance, so you can easily see the effect of the optimization. Check a C implementation of the same optimization at https://github.com/cgbarros/Pascal-Triangle-in-C.