# Memoization and Dynamic Programming

Bart Massey

## Consider Fibonacci Numbers

• Recurrence F[1] = 1; F[2] = 1; F[n+2] = F[n] + F[n+1]

• Let phi = (1 + sqrt(5)) / 2, phi' = -1 / phi . Then

``````  F[i] = (phi^i - phi'^i) / sqrt(5)
``````

which is super-weird

• The size of F[i] as a function of i is O(phii) which is exponential in i

## Dumb Algorithm For Computing Fibonacci Numbers

``````    RECURSIVE FIBONACCI

F(i):
if i = 1 or i = 2
return 1
return F(i-1) + F(i-2)
``````
• Correct. Cost is, well, the program has the same form as the Fibonacci recurrence itself, so this is an exponential algorithm O(phii)

## Memoization

``````    MEMOIZED RECURSIVE FIBONACCI

F(i):
if i = 1 or i = 2
return 1
v <- memo[i]
if v exists
return v
v <- F(i-1) + F(i-2)
memo[i] <- v
return v
``````
• Never evaluates F for a given i more than once

• Fast lookup is helpful: constant time lookup means F(i) in O(i)

• Note that there are still big additions

## Dynamic Programming

``````    DYNAMIC PROGRAMMING FIBONACCI

result[1] <- 1
result[2] <- 1
for j <- 3 .. i
result[j] <- result[j - 1] + result[j - 2]
return result[i]
``````
• Iterative now. Memo table replaced with simple array

• O(i) running time and space

• Don't really need all that memory, since once we've used a value twice we never touch it again.

``````  LOW MEMORY USE DYNAMIC PROGRAMMING FIBONACCI

result[1] <- 1
result[2] <- 1
for j <- 3 .. i
f <- result[1] + result[2]
result[1] <- result[2]
result[2] <- f
return result[2]
``````

## Factorial

• 0! = 1; n! = n * (n-1)! [n > 0]

``````  def fact(n):
if n == 0:
return 1
return n * fact(n - 1)
``````
• Memoized

``````  facts = dict()
facts[0] = 1
facts[1] = 1

def fact_memo(n):
if n in facts:
return facts[n]
result = n * fact(n - 1)
facts[n] = result
return result
``````
• DP

``````  def fact_dp(n):
fs = []
fs[0] = 1
for i in range(1, n + 1):
fs[i] = i * fs[i - 1]
return fs[n]
``````
• DP with O(1) mem

``````  def fact_dp_o1mem(n):
f = 1
for i in range(1, n + 1):
f *= i
return f
``````

## Memoization / Dynamic Programming is General

• Can use this same approach on other recurrences

• Can really cut down on running time and space

## Optimal Substructure

• For DP / memoization to work, need that larger indices depend only on smaller indices: can combine smaller solutions to get a larger one

• This is essentially an induction requirement

• Ackermann's and Collatz functions

• True optimization: can't make running time asymptotically worse

• Can run out of memory, though

## Largest Contiguous Subsequence Sum

• Also known as MAXIMUM SUBARRAY

``````  LARGEST CONTIGUOUS SUBSEQUENCE SUM

Given: A sequence s of integers.

Find: The largest sum over all contiguous subsequences of s.
``````
• Caveat: The sum of the empty subsequence is 0, so the minimum CSS should be 0

• If you want to always return sum of at least one element, easy to fix up: replace any 0 sum with the maximum array element. In this case, |s| > 0 or it won't work

## Largest Contiguous Subsequence Sum: Brute Force

``````    LCSS-BF(s):
m <- 0
for i in 1..|s|
t <- 0
for j in i..|s|
t <- t + s[j]
m <- max(m, t)
return m
``````
• Correctness: easy; Complexity: O(|s|^2)

## Largest Contiguous Subsequence Sum: Divide and Conquer

• Idea: The largest subsequence is either in the left half, in the right half, or crosses the middle. In the last case, can just extend from the middle toward each end and keep track of maximum sum

``````  LCSS-DC(s):
if |s| = 0
return 0
split <- |s| div 2
m <- LCSS-DC(s[1..split])
m <- max(m, LCSS-DC(s[split+1..|s|]))
ml <- 0
t <- 0
for i in split downto 1
t <- t + s[i]
ml <- max(ml, t)
mr <- 0
t <- 0
for i in split+1..|s|
t <- t + s[i]
mr <- max(mr, t)
return max(m, ml + mr)
``````
• Correctness: Induction on |s|. Complexity: O(|s| lg |s|)

## Largest Contiguous Subsequence Sum: Dynamic Programming

• Optimal substructure table for end position

• ``````  LCSS-DP(s):
d <- new array of length |s|
d[1] <- max(s[1], 0)
for i <- 2..|s|
d[i] <- max(s[i], d[i-1] + s[i])
return max(d)
``````
• Correctness: by induction on index of d. Time complexity: O(|s|)

• Space complexity: O(|s|), but this is easy to fix…

## Largest Contiguous Subsequence Sum: Kadane's Algorithm

``````    LCSS-KALDANE(s):
d <- max(s[1], 0)
m <- d
for i <- 2..|s|
d <- max(s[i], d + s[i])
m <- max(m, d)
return m
``````
• Correctness: Transformation from DP solution. Time complexity: O(|s|). Space complexity: O(1)

• Can easily modify to save ending index. Can use that to count back to starting index, or can track starting index also with minor modification

## DP Turns The Crank

• Coming up with Kadane's algorithm directly is pretty tricky