5. Dynamic Programming

Memoisation

Fibonacci can be defined as a recurrence relation: $f(n) = f(n - 1) + f(n - 2)$ . However, this approach is inefficient due to lots of duplicate calls: when expanded, it becomes $f(n) = f(1)+ f(1) + f(1) + \dots$ .

One solution to this is memoisation: the caching of results.

General Purpose Memoiser

def memoise(f):
  known = {}
  def new_func(*params):
    if param not in known:
      known[param] = f(*params)
    return known[params]
  return new_func

@memoise
def function_definition():

# Or use the built in tools:
from func_tools import lru_cache
# LRU: least recently used; gets rid of oldest result once number of results stored reaches `maxsize`

@lru_cache(maxsize = None)
def function_definition():
  // ...

Notes:

A nested function has access to variables within the outer function’s scope
*param in the function definition returns a tuple, *param passes the elements of the tuple individually as arguments
@func acts as a decorator that takes the function as an argument and modifies it

Fibonacci, Iteratively

Bottom-up iteration:

def fibonacci_i(n):
  a, b = 0, 1
  for i in range(n):
    a, b = b, a + b
  return a

This approach is $O(n)$ in time and $\Theta(1)$ in space.

Top-down Dynamic Programming

Recursion and memoisation.

Bottom-up Dynamic Programming

Store a table of solutions, solving the simplest sub-problems first
Fill out the table by combining sub-problems until target problem is reached

Example: Minimum Cost Path

Rectangular grid of cells, each with a weight. You can move to any adjacent cell (including diagonals) from each cell. Find the minimum cost needed to get from top to bottom.

Recurrence formula

$C_{i, j}$ is optimal cost of getting to the cell $(i,j)$ where $i\in [0, I)$ , $j\in[0, J)$ :

C_{i,j} = \begin{cases} \infty &\text{cell outside of the grid}\\ W_{i,j} &i = 0 \text{ (cell is at the the top of the grid)} \\ W_{i,j} + \min_{k\in(j-1, j, j+1)}(C_{i-1, k}) &\text{otherwise} \end{cases}

Hence in the normal case, the cost of the cell is the cell weight plus minimum cost to get to cell above it (left, directly above, or right).

Using a top-down approach:

Infinite cost if outside grid
Top row: just get the weight of the cell
Otherwise
- Check cache, return if found
- Find the minimum cost of the cells above/neighboring it
- Add the weight of the cell
- Save it to cache and return
Find the cost for each cell in the bottom row, and find the minimum from there

Using a bottom-up approach::

Create a table of all cells
Get weights for top row
For all cells in second row, find the minimum cost to get to that cell and add the cost of that cell
Repeat for all rows
Find the minimum-cost path by backtracking
- This is easier if you store the column of the cell you came from while generating the table

If the grid is square, it is $O(n^2)$ in time and space.

This problem can also be found using Dijkstra’s shortest path by converting the problem to a multi-stage graph (with weights moved to edges). However, this is harder to implement and less efficient.

Suitably of DP

DP approaches are likely to work when the problem:

Is combinatorial: brute force solution of either or
Involves only integers or slices of fixed strings with well-define bounds: a finite search domain
Is looking for the optimal solution

Then build the solution from solutions to sub-problems:

Requires optimal substructure
Expect overlapping subproblems
- Otherwise, the cache is useless
- NB: cache will often require the path to the result

Optimal Substructure

When solutions to subproblems can be reused (multiple times!) to find the optimal solution to the problem.

For example, in the shortest path problem, the shortest path for a sub-problem will be inside the shortest path for the larger problem.

The longest path problem does not have an optimal substructure.

Properties of Recursive Solutions

Want to make a cache of all the calls you make
How many unique function calls is it possible to make? How big could the cache be?
- For $fn(x_1, \dots, x_n)$ , the cache would be $|domain(x_1)| \cdot \dots \cdot |domain(x_n)|$
- Hence, this can become very large

Coin Changing Problem

A greedy approach does not produce optimal results. Hence, DP must be used.

Top-Down

Given coinage = [1, 10, 25] and amount = 80, the solution will always be minimum of:

1 + change(80 - 25, coinage, 3): the solution given all three coins are available
OR change(80, coinage, 2): the solution given only the first two coins are available

Either amount or coinage decreases to decrease the size of the problem.

An alternative approach would be finding the minimum of:

1 + change(80 - 1, coinage)
1 + change(80 - 10, coinage)
1 + change(80 - 25, coinage)

That is 1 + min(coinage_calculate(amount - coin, coinage) for coin in coinage)

Without memoisation, there are a maximum of len(coinage) sub-calls per call. With memoisation, the graph collapses to amount + 1 calls:

The number of coins is the same for every call (given the second approach). Hence, the only varying argument is the amount.
This would be inefficient using LRU cache as it would save both arguments for each call. Hence:
- Pass home-grown cache as an argument or
- Define an inner function and use LRU cache on that instead

0/1 Knapsack

No fractional amounts. For each item you have two options:

Pick up the item: get a smaller knapsack that can carry $W-w_i$ and have a current worth of $v_i$
Don’t pick up the item: get a knapsack that can carry $W$ and have a current worth of $0$

Repeat for each item, picking the option that gives the greater worth.

Edge cases:

No more items
Item can’t fit

Cache using index of item ( $i$ ) and weight of knapsack ( $C$ ): $$ V(i, c) = \begin{cases} 0 &i < 0 \ V(i-1, C) &i\ge 0, w_i > C \ \max(V(i-1, c), v_i + V(i-1, C-w_i)) &i\ge0, w_i \le c \end{cases} $$ This is easier when using 1 indexing: length and index are the same.

Top-Down

The number of possible calls is $nC$ , where $n$ is the number of items, and each function call will call two other calls until it reaches the base case.

If using LRU cache, run the computation in in a nested function using LRU cache, and store the array of items outside the scope of the function.

Bottom-Up

Generate table of knapsack weight (column) and index (row), filling table row-wise. Go backwards to reconstruct solution.

1 indexing is also useful in this case, in which an extra row and column (0) will be needed.

For each cell, you have two options:

Don’t pick up: go to the value of cell directly above
Pick up: value of item plus value of the cell one row above and $w_i$ to the left

Take the maximum of these two options.

This has a time and space complexity of $O(nW)$ . If only the maximum value and not the path is required, only two rows are needed. Hence, the space complexity gets reduced to $O(W)$ .

NB: this is pseudo-polynomial time - it is polynomial with the size of the knapsack, not the number of items.

Assuming the path is required, use backtracking to reconstruct the solution: start at the end, and If the value of the item directly above is the same, it means the optimal solution came from not picking up the item. Else, go up one and left by the weight of the item. This has a complexity of $O(n)$ .

Subset Sum Problem

Given a set of integers, find a subset that sums to zero.

Generalize this to finding a subset that sums to some value $S$ .

def subset_sum_exists(numbers, n, required_sum)
# returns true iff subset within first n elements that sum to required_sum

Longest Common Subsequence

Given two strings $A$ of length $n$ and $B$ of length $m$ , find the length of longest subsequence common to both strings. Characters do not need to be contiguous.

Brute forcing this is not possible - there are $2^n-1$ subsequences of $A$ , and determining if it is a subsequence of $B$ would take $O(m$ ) time. Hence, the time complexity of brute forcing a solution is $O(m\cdot 2^n)$ .

Create a function, $L_{i,j}$ , which returns the longest common subsequence given substrings of $A$ and $B$ : $A=a_1a_2\dots a_i$ and $B=b_1b_2\dots b_j$ . $$ L_{i,j} = \begin{cases} 0 & i = 0 \text{ or } j = 0 \ L_{i-1, j-1} + 1 & a_i = b_j \ \max(L_{i, j-1}, L_{i-1, j}) & a_i \neq b_j \end{cases} $$

Bottom-Up

Create a table of 1-origin subscripts for all possible values of $L_{i, j}$ , initializing $L_{0, j} = 0$ . Then, built up the table row-by-row:

If $a_i = b_j$ , add 1 to the value of the cell one row up and one column to the left
Else, get the max of either the cell to the left or the cell above

Edit Distance

The diff algorithm. Transform source string $A = a_1\dots a_n$ into $B = b_1\dots b_m$ using the minimum number of insertions, deletions, and substitutions. This number is called the edit distance.

When a transformation is not needed, it is called the alignment operation, and has zero cost.

Work from end of string to start.

Copy/Alignment: If $a_i = b_j$ , $D_{i,j} = D_{i-1, j-1}$
Otherwise, use the minimum of:
- Deletion: $D_{i,j} = D_{i-1,j} + 1$
- Insertion: $D_{i,j} = D_{i, j-1} + 1$
- Substitution: $D_{i,j} = D_{i-1, j-1} + 1$
  - Prefer substitution over deletion/insertion $$ D_{i, j} = \begin{cases} 0 & i = j = 0 \ i & j = 0 \ j & i = 0 \ D_{i-1, j-1} & a_i = b_j \ 1 + \min(D_{i-1, j}, D_{i, j-1}, D_{i-1, j-1}) & \text{otherwise} \end{cases} $$

Longest Increasing Subsequence

One solution is to sort, remove duplicates, and then run LCS on the two sequences. However, a more efficient solution is possible.

Let $L_j$ be the length of the longest increasing substring up to and including position $s_j$ in the string $s\dots s_n$ .

Recurrence relation: find the maximum of LIS for all solutions before the current index, provided the last (and so biggest) element is smaller than the current element.

L_j = \begin{cases} i & i=1, s_j \ge s_i \; \forall 0 < j < i \\ 1 + \max_{0<j<i, \; s_j < s_i}{L_j} & \text{otherwise} \end{cases}

This can be further optimized into an $O(n\log{n})$ solution: optional sequences are in increasing order, so a binary search can be done instead of searching all elements before it.