Dynamic Programming¶

Example 1: Factorial & Fibonacci functions¶

Evaluate the runtime for the factorial and fibonacci functions for n=50 using %timeit

def Factorial(n):
    if n<=1:
        return 1
    return n*Factorial(n-1)

def Fibonacci(n):
    if n in [0,1]:
        return n
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2)

n=20
%time print(f'Factorial({n})={Factorial(n)}')
print('\n')
%time print(f'Fibonacci({n})={Fibonacci(n)}')

Factorial(20)=2432902008176640000
CPU times: user 283 µs, sys: 141 µs, total: 424 µs
Wall time: 364 µs


Fibonacci(20)=6765
CPU times: user 3.2 ms, sys: 135 µs, total: 3.33 ms
Wall time: 3.85 ms

Memoization Pseudo code (top down);¶

Define an empty array the same size as the number of steps we intend to iterate
Define a function that accepts the array and a discrete number n
specify the initial conditions,
if the value of n meets the initial conditions, return them
if theres a saved value for array[n], return that value
other wise, use the recursion relation with the function in step 2 to calculate the specific value, and save it to an array

Example 2: Fibonacci via memoization¶

Design the Fibonacci function with memoization (top down) in dynamic programming and evaluate the run time for n=20, compare it to the run time WITHOUT memoization

def fibonacci_memo(n):
    array = [None]*(n+1)
    def fibonacci_top_down(n,array):
        if array[n] is not None:
            return array[n]
        if n in [1,2]:
            result=1
        else:
            result=fibonacci_top_down(n-1,array)+fibonacci_top_down(n-2,array)
        array[n]=result
        return result
    return fibonacci_top_down(n,array)

n=20
%time print(f'fibonacci_memo({n})={fibonacci_memo(n)}')
print('\n')
%time print(f'fibonacci({n})={Fibonacci(n)}')

fibonacci_memo(20)=6765
CPU times: user 437 µs, sys: 182 µs, total: 619 µs
Wall time: 523 µs


fibonacci(20)=6765
CPU times: user 3.16 ms, sys: 243 µs, total: 3.41 ms
Wall time: 3.58 ms

Bottom up Pseudo Code¶

define a function that accepts a discrete number n
define an empty array of size n+1
In the empty array, specify the values for initial conditions for n=0, n=1, etc
loop through the values between just above the initial condition values (e.g. n=2) and to the value of n+1
At each iteration of the loop, perform the recursive calculation using the array values and save it to the array.
Make the function return the saved value of the array, array[n]

Example 3: Factorial Bottom up¶

Design the Factorial function with bottom up in dynamic programming and evaluate the run time for the following values of n; [20,100,1000] and compare it to the original function.

What do these results say about using dynamic programming?

def factorial_bottom_up(n):
    bottom_up = [None]*(n+1)
    bottom_up[1]=1
    for i in range(2,n+1):
        bottom_up[i] = i*bottom_up[i-1]
    return bottom_up[n]

for n in [20,100,1000]:
    %time print(f'factorial_bottom_up({n})={factorial_bottom_up(n)}')
    print('\n')
    %time print(f'factorial({n})={Factorial(n)}')
    print('\n')

factorial_bottom_up(20)=2432902008176640000
CPU times: user 208 µs, sys: 94 µs, total: 302 µs
Wall time: 264 µs


factorial(20)=2432902008176640000
CPU times: user 64 µs, sys: 21 µs, total: 85 µs
Wall time: 89.9 µs


factorial_bottom_up(100)=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
CPU times: user 257 µs, sys: 100 µs, total: 357 µs
Wall time: 313 µs


factorial(100)=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
CPU times: user 62 µs, sys: 15 µs, total: 77 µs
Wall time: 69.9 µs


factorial_bottom_up(1000)=402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
CPU times: user 663 µs, sys: 123 µs, total: 786 µs
Wall time: 751 µs


factorial(1000)=402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
CPU times: user 988 µs, sys: 101 µs, total: 1.09 ms
Wall time: 1.02 ms

Example 4: Runing Sum - bottom up¶

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Reference: https://leetcode.com/problems/running-sum-of-1d-array/

e.g. Input: nums = [1,2,3,4] Output: [1,3,6,10]

e.g. Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5]

from typing import List
def runningSum(nums: List[int]) -> List[int]:
    #bottom up approach
    n = len(nums)
    bottom_up = [None]*(n)
    bottom_up[0] = nums[0]
    for j in range(1,n):
        bottom_up[j] = nums[j]+bottom_up[j-1]
    return bottom_up

runningSum([1,2,3,4])

[1, 3, 6, 10]

Example 5: Running Sum - memoization¶

def runningSumMemo(nums: List[int]) -> List[int]:
        ans = []
        def cumsum(ind):
            if ind == 0:
                return nums[ind]
            return nums[ind] + cumsum(ind-1)
        for i in range(len(nums)):
            ans.append(cumsum(i))
        return ans

runningSumMemo([1,2,3,4])

[1, 3, 6, 10]