Dynamic Programming For Coding Interviews: A Bottom-Up Approach To Problem Solving

I wanted to compute 80th term of the Fibonacci series. I wrote the rampant recursive function <p/> int fib(int n){ <p/> return (1==n 2==n) ? 1: fib(n-1) + fib(n-2); <p/> } <p/> and waited for the result. I wait... and wait... and wait... <p/> With an 8GB RAM and an Intel i5 CPU why is it taking so long? I terminated the process and tried computing the 40th term. It took about a second. I put a check and was shocked to find that the above recursive function was called 204668309 times while computing the 40th term. <p/> More than 200 million times? Is it reporting function calls or scam of some government? <p/> The Dynamic Programming solution computes 100th Fibonacci term in less than fraction of a second with a single function call taking linear time and constant extra memory. <p/> A recursive solution usually neither pass all test cases in a coding competition nor does it impress the interviewer in an interview of company like Google Microsoft etc. <p/> The most difficult questions asked in competitions and interviews are from dynamic programming. This book takes Dynamic Programming head-on. It first explain the concepts with simple examples and then deep dives into complex DP problems.