Dynamic programming

Page 1

Dynamic programming and greedy method both are for optimization.

unlike greedy method we here discover all possible answers and then select the most optimized one

time consuming

we use recursive formulas here

we here use principal of optimality

principal of optimality- here we take sequence of decisions to get the optimal solution. i.e, at every stage we take a decision

here we use tabuliation and memorization method

now

let's take an example of Fibonacci series by using recursion

time complexity is O[2^n] which is alot

as we see the tree we have called f(2) or f(1) multiple times so we will reduce it(memorization approach)

so these will be stored

we make a array on getting ex f(2) we store in index 2 of the array

here we only call it for 6 times in the tree

i.e, for n= n+1 calls so T(n)=O[n]

memorization approach-----top-down approach

1) the tree is created

2) the representative functions are ignored

3) the result is obtained back

tabluatzation approach--------bottom-up approach(it doesn't use recursion)

here we start the loop from 2 instead of 1 in the algorithm

we fill the existing value by adding two previous values.