Fibonacci Numbers using DP

Prerequisite: Recursion

N = 4

This recursion has exponential time complexity, as the recursion tree grows significantly when n increases.

For example, if n = 6.

Overlapping Subproblems:

As you can see, some subproblems repeat. If you encounter the same subproblems again and again, this is known as overlapping subproblems.

Optimal Substructure:

When solving smaller subproblems helps in solving the bigger problem, the problem is said to have an optimal substructure.

Note:

If any problem satisfies these two properties (overlapping subproblems and optimal substructure), it is an ideal candidate for Dynamic Programming (DP).

Time Complexity:

• The time complexity of this problem using plain (naive) recursion is O(2n).
• Now, applying DP to this problem: DP works on the DRY (Don’t Repeat Yourself) principle. Instead of recalculating overlapping subproblems, we save their results and reuse them.

In this above image (Focus on the left side -→ it symbolizes an arrow), we maintain a storage (memoization table or DP array) to keep previously computed results.

• By doing this, we can fetch already computed results from the storage. This way, we don’t need to calculate the same subproblems again and again.
• By storing these values, the time complexity reduces from O(2n) to O(n)..

Fib(100):

This would take longer than universe’s age with naive recursion, but with DP you can solve it instantelously.

Fib(n):

where n is for bigger values.

Exponential growth leads to Astronomically large number of operations, making it computationally infeasible within a reasonable timeframe.

DP Vs Greedy: (When to use:)

• Greedy: Make the best local choice and hope to reach the Global Optimal Solution.
• DP: Explore all possibilities store result of subproblem and reach the result.