#!/usr/bin/env python
# coding: utf-8
# # Dynamic Programming (DP)
#
#
# - https://www.cs.cmu.edu/~avrim/451f09/lectures/lect1001.pdf
# - https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/
# - powerful technique that allows one to solve many different types of problemns in time $O(n^2)$ or $O(n^3)$ for which a naive approach would take exponential time
# - two main properties of a problem that warrents DP solution:
# 1. Overlapping Subproblems
# 2. Optimal Substructures
# ## Overlapping Subproblems
# - problem combines solutions from many overlapping sub-problems
# - DP is not useful when there are no common (overlapping) subproblems
# - computed solutions to sub-problems are stored in a look-up table to avoid recomputation
# - slighlty different from **Divide and Conquer** technqiue
# - divide the problems into smaller non-overlapping subproblems and solve them independently
# - e.g.: merge sort and quick sort
#
# ## Optimal Substructures
# - optimal solution of the given problem can be obtained by using optimal solutions of its subproblems
# ## 2 Types of DP solutions
#
# ## 1. Top-Down (Memoization)
# - based on the Latin word memorandum, meaning "to be remembered"
# - similar to word memorization, its a technique used in coding to improve program runtime by memorizing intermediate solutions
# - using dict type lookup data structure, one can memorize intermediate results of subproblems
# - tpically recursion use top-down approach
#
# ### Process
# - start solving the given problem by breaking it down
# - first check to see if the given problem has been solved already
# - if so, return the saved answer
# - if not, solve it and save the answer
#
# ## 2. Bottom-Up (Tabulation)
# - start solving from the trivial subproblem
# - store the results in a table/list/array
# - move up towards the given problem by using the results of subproblems
# - typically iterative solutions uses bottom-up approach
# ### simple recursive fib function
# - recall, fibonacci definition is recursive and has many common/overlapping subproblems
#
# In[1]:
count = 0
def fib(n):
global count
count += 1
if n <= 1:
return 1
f = fib(n-1) + fib(n-2)
return f
n=30 #40, 50? takes a while
print("fib at {}th position = {}".format(n, fib(n)))
print("fib function count = {}".format(count))
# ### theoritical computational complexity
# - Time Complexity: $T(n)$ = time to calculate Fib(n-1) + Fib(n-2) + time to add them: O(1)
# - using Big-Oh (O) notation for upper-bound:
# - $T(n) = T(n-1) + T(n-2) + O(1)$
# - $T(n) = O(2^{n-1}) + O(2^{n-2}) + O(1)$
# - $T(n) = O(2^n)$
#
# **precisely**
# - $T(n) = O(1.6)^n$
#
# - 1.6... is called golden ratio - https://www.mathsisfun.com/numbers/golden-ratio.html
# - Space Complexity = $O(n)$ due to call stack
# In[8]:
#print(globals())
import timeit
print(timeit.timeit('fib(30)', number=1, globals=globals()))
# big difference between 30 and 40
# ### memoized recursive fib function
# In[9]:
count = 0
def MemoizedFib(memo, n):
global count
count += 1
if n <= 1:
return 1
if n in memo:
return memo[n]
memo[n] = MemoizedFib(memo, n-1) + MemoizedFib(memo, n-2)
return memo[n]
# In[11]:
memo = {}
n=1000 #try 40, 50, 60, 100, 500, 10000, ...
print("fib at {}th position = {}".format(n, MemoizedFib(memo, n)))
print("fib function called {} times.".format(count))
# In[21]:
import timeit
memo = {}
n=1000
print(timeit.timeit('MemoizedFib(memo, n)', number=1, globals=globals()))
# ### computational complexity of memoized fib
# - Time Complexity - $O(n)$
# - Space Complexity - $O(n)$
# ### normally large integer answers are reported in mod $(10^9+7)$
# - mod of a farily large prime number
# - need to know some modular arithmetic: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction
# - $(A+B) \% C = (A \% C + B \% C) \% C$
# - $(A-B) \% C = (A \% C - B \% C) \% C$
#
# In[15]:
mod = 1000000007
def MemoizedModFib(memo, n):
if n <= 1:
return 1
if n in memo:
return memo[n]
memo[n] = (MemoizedFib(memo, n-1)%mod + MemoizedFib(memo, n-2)%mod)%mod
return memo[n]
# In[17]:
memo = {}
n=1000 #try 40, 50, 60, 100, 500, 10000, ...
print("fib at {}th position = {}".format(n, MemoizedModFib(memo, n)))
# ### bottom-up (iterative) fibonacci solution
# - first calculate fib(0) then fib(1), then fib(2), fib(3), and so on
# In[22]:
def iterativeFib(n):
# fib array/list
fib = [1]*(n+1) # initialize 0..n list with 1
for i in range(2, n+1):
fib[i] = fib[i-1] + fib[i-2]
return fib[i]
# In[24]:
n=1000
print(timeit.timeit('iterativeFib(n)', number=1, globals=globals()))
# is faster than recursive counterpart
# ## Coin Change Problem
# - https://www.geeksforgeeks.org/understanding-the-coin-change-problem-with-dynamic-programming/
# - essential to understanding the paradigm of DP
# - a variation of problem definition:
# - Given a infinite number of coins of various denominations such as $1$ cent (penny), $5$ cents (nickel), and $10$ cents (dime), can you determine the total number of combinations (order doesn't matter) of the coins in the given list to make up some amount $N$?
# - Example 1:
# - Input: coins = $[1, 5, 10]$, $N = 8$
# - Output: 2
# - Combinations:
# 1. $1 + 1 + 1 + 1+1+1+1+1 = 8$
# - $1 + 1 + 1 + 5 = 8 $
# - Example 2:
# - Input: coins = $[1, 5, 10], N = 10$
# - Output: 4
# - Combinations:
# 1. $1+1+1+1+1+1+1+1+1+1=10$
# - $ 1+1+1+1+1+5 = 10$
# - $ 5+5 = 10$
# - $10 = 10$
# - Implementation:
# - we use tabulation/list/array to store the number of ways for outcome $N = 0$ to $12$
# - values of list represent the number of ways; indices represent the outcome/sum $N$
# - so ways = [0, 0, 0, 0, 0, 0....] initialized with 12 0s
# - base case:
# - ways[0] = 1; there's 1 way to make sum N=0 using 0 coin
# - for each coin:
# - if the value of coin is less than the outcome/index $N$,
# - update the ways[n] = ways[n-coin] + ways[n]
# In[43]:
def countWays(coins, N):
# use ways table to store the results
# ways[i] will store the number of solutions for value i
ways = [0]*(N+1) # initialize all values 0-12 as 0
# base case
ways[0] = 1
# pick all coins one by one
# update the ways starting from the value of the picked coin
print('values:', list(range(N+1)))
for coin in coins:
for i in range(coin, N+1):
ways[i] += ways[i-coin]
print('ways: ', ways, coin)
return ways[N]
# In[44]:
coins = [1, 5, 10]
N = 8
print('Number of Ways to get {} = {}'.format(N, countWays(coins, N)))
# In[45]:
N = 10
print('Number of Ways to get {} = {}'.format(N, countWays(coins, N)))
# In[46]:
N = 10
print('Number of Ways to get {} = {}'.format(N, countWays(coins, 12)))
# ## find minimum number of coins that make a given value/change
# - Problem:
# - Input: $coins = [5, 10, 25], N = 30$
# - Output: 2
# - Combinations: $25 + 5 = 30$
# In[50]:
import math
# DP solution for min coin count to make the change N
def minCoins(coins, N):
# count list stores the minimum number of coins required for i value
# all values 0-N are initialized to infinity
count = [math.inf]*(N+1)
# base case
# no. of coin required to make 0 value is 0
count[0] = 0
# computer min coins for all values from 1 to N
for i in range(1, N+1):
for coin in coins:
# for every coin smaller than value i
if coin <= i:
if count[i-coin]+1 < count[i]:
count[i] = count[i-coin]+1
return count[N]
# In[51]:
coins = [1, 3, 4]
N = 6
print('min coins required to give total of {} change = {}'.format(N, minCoins(coins, N)))
# ## Exercises
# 1. Ocean's Anti-11 - https://open.kattis.com/problems/anti11
# - Hint: count all possible n length binary integers (without 11) for the first few (2,3,4) positive integers and you'll see a Fibonaccii like pattern that gives the total number of possible binaries without 11 in them
# - Write a program that finds factorials of a bunch of positive integer numbers. Would memoization improve time complexity of the program?
# In[ ]: