DEV Community

Cover image for Dynamic Programming Series - Introduction

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
Collapse
 
jvanbruegge profile image
Jan van Brügge •

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);
}
Enter fullscreen mode Exit fullscreen mode

this is similar to the for loop

Collapse
 
ankursheel profile image
Ankur Sheel •

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.

Collapse
 
mortoray profile image
edA‑qa mort‑ora‑y •

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. :)

Collapse
 
ankursheel profile image
Ankur Sheel • • 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.

Collapse
 
ollpu profile image
Roope Salmi •

Oh, further optimization is possible. For example, with matrix exponents ;)

Collapse
 
ankursheel profile image
Ankur Sheel •

Haha. You got me there. I should have specified no further optimizations from a DP perspective :)

Collapse
 
wozaisuzhou profile image
Danny •

Another solution , probably can take a look at :

dev.to/wozaisuzhou/algorithms-chal...

Collapse
 
joshcheek profile image
Josh Cheek •

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).

Collapse
 
ankursheel profile image
Ankur Sheel •

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?

Collapse
 
amlace profile image
Suraj •

Wonderful post :-) Cleared up a lot of concepts for me.

Collapse
 
ankursheel profile image
Ankur Sheel •

Thanks Suraj.