Advanced Dynamic Programming

Introduction

Prerequisites: Dynamic Programming

Dynamic programming is very powerful and more efficient than recursion for problems that recompute multiple values. However sometimes it is difficult to find an efficient dynamic programming solution and we will examine problems where we will need higher dimensions.

Longest Common Subsequence

A subsequence is a subset of the original sequence that is in the same order. For example in the string "abcdefghi", "aeg" is a subsequence but "eaq" is not because it is not in order.

The longest common subsequence between two strings A and B is the longest subsequence in A that is also in B.

For example, given A="xyaaaabcdeg", B="bcaaaaefgxy" the longest common subsequence is "aaaaeg".

xyaaaabcde_g
bcaaaa___efgxy

If we try to use greedy we will see it doesn't work. For example, if we use try to take as much as B as we can, we see that we will get BCEG or if we try to take as much as A we get XY.

Let first write a formal definition of the problem, given two strings A and B each with lengths N and M respectively, we want to find the longest common subsequence between them.

The base case is very simple: if A or B are empty strings, then trivially, the longest common subsequence is an empty string.

Now suppose that A and B are non empty strings. Let's consider the case that A and B both start with the same letter (A[0] == B[0]). It can be seen that the longest common subsequence must also begin with that letter. Thus the longest common subsequence is A[0] plus the longest common subsequence from A[1..N] and B[1..M]. However, suppose that A and B do not start with the same letter (A[0] != B[0]). Then the LCS of A and B is either the LCS of A[1..N] and B or the LCS of A and B[1..M] and we take the longer of the two. Thus, this is our recurrence relation.

Formalization

Let lcs(A, B) be the longest common substring between A and B.
Let N be the length of A and M be the length of B.
Let max(A, B) be the string with longer length.

lcs('', A) = ''
lcs(B, '') = ''

lcs(A, B) = A[0] + lcs(A[1..N], B[1..M]) if A[0] == B[0]
lcs(A, B) = max(lcs(A, B[1..M]), lcs(A[1..N], B)) otherwise

Example:
lcs('AB', 'CAB')
= max(lcs('AB','AB'), lcs('A', 'CAB'))
= max('A' + lcs('B', 'B'), max(lcs('A', 'AB'), lcs('', 'CAB'))
= max('A' + 'B' + lcs('', ''), max('A' + lcs('', 'B')), ''))
= max('AB', max('A', ''))
= max('AB', 'A')
= 'AB'

Example:
lcs('XY', 'AB')
= max(lcs('XY', 'B'), lcs('Y', 'AB'))
= max(max(lcs('XY',''), lcs('Y', 'B')), max(lcs('Y','B'), lcs('', 'AB'))
= ''

Note that in the second example, we are recomputing lcs('Y', 'B') twice. If we have longer strings, we will be recomputing the same values many times! We can rewrite the solution with dynamic programming by building up the solution instead of using recursion and eliminating recomputation.

Let lcs[x][y] be the least common subsequence of A[0..x] and B[0..y].
Let N be length of A and M be length of M

// Base case
for i from 1 to N
  lcs[i][0] = ''

// Base case
for i from 1 to M
  lcs[0][i] = ''

for x from 1 to N
  for y from 1 to M
    if A[x - 1] == B[j - 1]
      lcs[x][y] = lcs[x - 1][y - 1] + A[x - 1]
    else
      lcs[x][y] = max(lcs[x - 1][y], lcs[x][y - 1]


Example (string lengths):
A = 'xygz'
B = 'yabz'

      x y g z
  / 0 1 2 3 4
  0 0 0 0 0 0
y 1 0 0 1 1 1
a 2 0 0 1 1 1
b 3 0 0 1 1 1
z 4 0 0 1 1 2

Zero-One Knapsack Problem

In the Dynamic Programming section, we examined the knapsack problem:

Given an unlimited amount of N items with positive weights and values, we want to find the maximum value we can hold with a capacity.

Let's change the problem slightly such that there is only one of each object. The problem becomes slightly more difficult because we need to take into account whether or not we have used an object before.

Given only one copy each of N items with positive weights and values, we want to find the maximum value we can hold with a capacity W.

The base case is simple, if there are no more items or the total capacity is less than or equal to 0, then the maximum value is 0. Suppose we have items remaining and total capacity is positive. We can either take or leave the first item and we want the maximum value of both actions. If we take the item, the value will be the value of the item plus the maximum value of the rest of the items that fit in the rest of the space in the knapsack minus the space of the item we took. If we leave the item, the value will be the maximum value of the rest of the items that fit in the knapsack. Thus we have our recurrence relation.

Let knapsack(items[], W) be the maximum value of items that fit in a maximum capacity of W.
Let N be the number of items.

Base case:
knapsack(items[], w) = 0 if w <= 0
knapsack([], w) = 0

Recursion:
takeValue = knapsack(items[1..N], w - items[0].weight) + items[0].value
leaveValue = knapsack(items[1..N], w)
knapsack(items[], w) = max(takeValue, leaveValue)

However, we are recomputing multiple values and we can eliminate this by building the solution upwards using dynamic programming.

Let knapsack[N][W] be the maximum value of N items that fit in a maximum capacity of W.
Let items be an array of N items with positive weights and values.

for i from 0 to W
  knapsack[0][i] = 0

for n from 1 to N
  knapsack[n][0] = 0
  for w from 1 to W
    takeValue = knapsack[n - 1][w - item[n - 1].weight] + item[n - 1].value
    leaveValue = knapsack[n - 1][w]
    knapsack[n][w] = max(takeValue, leaveValue)