# 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(phi

^{i}) 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(phi
^{i})

## 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

C.f. https://stackoverflow.com/a/39082628

`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

Once the DP algorithm is in hand, Kadane is for free

But the DP algorithm can be gotten by staring at the brute-force algorithm and looking for optimal substructure