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

  • 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