Dynamic programming Introduction
Dynamic Programming Introduction Dynamic Programming is mainly an optimization over plain recursion . Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. For example, if we write simple recursive solution for Fibonacci Numbers , we get exponential time complexity and if we optimize it by storing solutions of sub problems, time complexity reduces to linear. Fibonacci Number using recursion and dynamic programming Let us start understand it with an example. Let us take example as fib(4) For fib(4), fib(0) will called twice , fib(1) will be called thrice , fib(2) will be called twice, fib(3) will be cal...