DEV Community

Dynamic Programming Series - Introduction

Ankur Sheel on April 01, 2017

This article has been cross-posted from here Dynamic Programming is one of those techniques that every programmer should have in their toolbox. Bu...

Read full post

Jan van Brügge • Apr 1 '17

You forgot that C++ has tail call optimization. This means you can run it in constant space:

long Fibbonacci(long n) {
    auto helper = [](long a, long b, long n) { return n > 0 ? helper(b, a+b, n-1) : a; }
    return helper(0, 1, n);
}

this is similar to the for loop

Ankur Sheel • Apr 2 '17

You are right about the tail call optimisation. However, that would have beaten the purpose of gearing this article towards beginners and also keeping it language agnostic. The main issue I have had with other articles (and that I wanted to avoid here) is that either they skip intermediate steps or use tricks which are not conducive to understanding the technique itself.

edA‑qa mort‑ora‑y • May 29 '17

You left in the #define MOD 1000000007 and % MOD which isn't part of the explanation. Though I recall see computing tests that have this requirement on them. :)

Ankur Sheel • May 29 '17 • Edited

I do mention the reason in the Top-Down Recursive approach with Memoization section. Re-iterating it here for your convenience We mod the result using 1000000007 to avoid overflows.

Josh Cheek • Apr 1 '17

Good article! I think C++ isn't the right language for it, though (syntactic noise, difficulty reproducing, the numbers are too large for it to handle).

Ankur Sheel • Apr 1 '17

Thanks Josh.

I feel that since it is a technique, it is not limited to a language. I guess it might be more accessible if it was in one of the newer languages. But, it's better to stick with a language you are comfortable with and I don't need to figure out a whole new benchmarking system :)
I could have written it in pseudocode but then the benchmarking would have been extremely difficult.

What would you suggest be done differently?