Dynamic_prog.py

# Fibonaci of 5 using recursion
def calc_fibonaci(n):
    if n<=1:
        return n
    return calc_fibonaci(n-1) + calc_fibonaci(n-2)
print(calc_fibonaci(6))

# Memoization
def calc_fibonaci(n):
    cache=[-1 for x in range(n+1)]
    if (cache[n] < 0):
        if (n==0):
            cache[n] = 0
        elif (n == 1):
            cache[n] = 1
        else:
            cache[n] = calc_fibonaci(n-1) + calc_fibonaci(n-2)
            
# Tabulation
def calc_fibonaci(n):
    tab=[0,1]
    for i in range(2,n +1):
        tab.append(tab[i-1] + tab[i-2])
    return tab[n]
print(calc_fibonaci(6))  
            
    return cache[n]

print(calc_fibonaci(6))

INF = 100000

# coin Minimization 
def coin_change_modified(denomination, amount, no_of_coins):
  No_of_ways = [0]*(amount+1)
  coins_for_amount = [0]*(amount+1)

  for j in range(1, amount+1):
    minimum = INF
    coin = 0

    for i in range(1, no_of_coins+1):
      if(j >= denomination[i]):
        minimum = min(minimum, 1+No_of_ways[j-denomination[i]])
        coin = i
    No_of_ways[j] = minimum
    coins_for_amount[j] = coin
    
  l = amount
  while(l>0):
    print(denomination[coins_for_amount[l]])
    l = l-denomination[coins_for_amount[l]]
    
  return No_of_ways[amount]

if __name__ == '__main__':
  # array starting from 1, element at index 0 is fake
  d = [0, 1,2,  5, 10]
  coin_change_modified(d, 9, 4) #to make 5. Number of denominations = 3

Dynamic programming is a technique to find an optimal solution to a complex recursive problem by breaking it down into simpler sub-problems and solving those sub-problems only once by storing the results of those sub-problems.