Dynamic Fibonacci

If we want to understand the true essence of dynamic programming, we should consider the simple example of fibonacci series. Using the conventional algorithm the time complexity of the solution is O(2^n).

 def fibonacci(n):
    i, a, b = 1, 0, 1
    while(i<=n):
         a, b = b, a+b
         i += 1
    return b

But using the dynamic programming we can reduce the function call, as well as the time complexity to O(n).

class Main {
 int[] f = new int[100];
 
 public int fibonacci(int n) {
       f[0] = f[1] = 1;
       for(int i=2;i<=n;i++) {
            f[i] = f[i-1] + f[i-2];
       }
 return f[n];
 }
}

Why is “dynamic programming?” & the key notes

Dynamic programming is the most influential paradigm in algorithm. It solves multiple key problems of computing.

Why is dynamic programming?

  • To reduce the function call (improves the time, and space complexity).
  • Breaks the whole problem into sub-problems (:only if the sub problems are similar to the whole problem, i.e. problems like Fibonacci series where each function call does the same thing).
  • Re-using the subproblems.
  • Anything else!?

Key Points for Dynamic Programming:

  • Recursion
  • Memoization (using the sub-solutions)

Further reading : dynamic programming