LCS, edit distance, knapsack and matrix chain

Why it exists

Four problems appear again and again in exams on dynamic programming, and between them they contain every idea a DP question uses: a two-index table over prefixes (LCS, edit distance), a table indexed by a capacity (knapsack), and a table indexed by intervals filled by increasing length (matrix chain). For each GATE asks you to write or read the recurrence, fill a small table, state the time and space, and recognise the traps (pseudo-polynomial time, the number of parenthesisations).

Prerequisites

You need the recipe of dynamic programming: state, recurrence, filling order, answer (dynamic programming).

Precise definitions

Subsequence. A string obtained by deleting zero or more letters, keeping the order ($\text{ACE}$ is a subsequence of $\text{ABCDE}$). Not necessarily contiguous (a substring is).

Longest common subsequence (LCS). The longest string that is a subsequence of both $x$ and $y$.

Edit distance (Levenshtein). The fewest operations that turn $x$ into $y$, where an operation is the insertion of a letter, the deletion of a letter, or the replacement of a letter by another (each costing $1$).

0/1 knapsack. Items $i = 1..n$ with weights $w_i$ and values $v_i$ (integers), capacity $W$; choose a subset of total weight at most $W$ with maximum total value. Each item is taken or left.

Matrix chain multiplication. Multiply $A_1 A_2 \cdots A_n$, where $A_i$ is $p_{i-1} \times p_i$. The product does not depend on the bracketing, but the cost does: multiplying a $p \times q$ matrix by a $q \times r$ matrix costs $pqr$ scalar multiplications. Find the bracketing with the fewest scalar multiplications (the order of the matrices is fixed, only the brackets are chosen).

How it works

Longest common subsequence

Let $L[i][j]$ be the length of an LCS of the first $i$ letters of $x$ and the first $j$ letters of $y$. Look at the last letters $x_i$ and $y_j$:

$L[i][j] = \begin{cases} 0 & i = 0 \text{ or } j = 0,\\ L[i-1][j-1] + 1 & x_i = y_j,\\ \max(L[i-1][j],\ L[i][j-1]) & x_i \ne y_j. \end{cases}$

If the letters are equal they can be matched at the end of an LCS (and matching them is never worse); if not, at least one of them is not used. Time and space $\Theta(mn)$: $(m+1)(n+1)$ entries, $O(1)$ each. To find the string, walk back from $L[m][n]$: if the letters are equal output the letter and go diagonally up-left; otherwise go to the larger of the neighbours above and to the left. If only the length is needed, two rows suffice: space $\Theta(\min(m, n))$.

Edit distance

Let $D[i][j]$ be the edit distance from the first $i$ letters of $s$ to the first $j$ letters of $t$:

The three terms in the minimum are: delete $s_i$ (move up), insert $t_j$ (move left), replace $s_i$ by $t_j$ (move diagonally). Time and space $\Theta(mn)$.

The program below computes the LCS of DYNAMIC and DANCING and the edit distance from SPRING to STRONG, and prints both tables.

#include <stdio.h>
#include <string.h>
 
static int max(int a, int b) { return a > b ? a : b; }
static int min3(int a, int b, int c) { return a < b ? (a < c ? a : c) : (b < c ? b : c); }
 
int main(void) {
    const char *x = "DYNAMIC", *y = "DANCING";
    int m = (int)strlen(x), n = (int)strlen(y);
    int L[8][8];                                         /* L[i][j] = length of a longest common subsequence of the first i letters of x and the first j of y */
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) L[i][j] = 0;
            else if (x[i - 1] == y[j - 1]) L[i][j] = L[i - 1][j - 1] + 1;
            else L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
    char lcs[8];
    int len = L[m][n];
    lcs[len] = 0;
    for (int i = m, j = n, k = len - 1; i > 0 && j > 0;) {       /* walk back from the corner */
        if (x[i - 1] == y[j - 1]) { lcs[k--] = x[i - 1]; i--; j--; }
        else if (L[i - 1][j] >= L[i][j - 1]) i--;
        else j--;
    }
    printf("LCS of %s and %s has length %d: %s\n", x, y, len, lcs);
 
    const char *s = "SPRING", *t = "STRONG";
    int p = (int)strlen(s), q = (int)strlen(t);
    int D[7][7];                                         /* D[i][j] = fewest edits turning the first i letters of s into the first j of t */
    for (int i = 0; i <= p; i++) {
        for (int j = 0; j <= q; j++) {
            if (i == 0) D[i][j] = j;
            else if (j == 0) D[i][j] = i;
            else if (s[i - 1] == t[j - 1]) D[i][j] = D[i - 1][j - 1];
            else D[i][j] = 1 + min3(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1]);
        }
    }
    printf("edit distance from %s to %s is %d\n", s, t, D[p][q]);
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) printf("%2d", L[i][j]);
        printf("\n");
    }
    for (int i = 0; i <= p; i++) {
        for (int j = 0; j <= q; j++) printf("%2d", D[i][j]);
        printf("\n");
    }
    return 0;
}

LCS of DYNAMIC and DANCING has length 3: DNI
edit distance from SPRING to STRONG is 2
 0 0 0 0 0 0 0 0
 0 1 1 1 1 1 1 1
 0 1 1 1 1 1 1 1
 0 1 1 2 2 2 2 2
 0 1 2 2 2 2 2 2
 0 1 2 2 2 2 2 2
 0 1 2 2 2 3 3 3
 0 1 2 2 3 3 3 3
 0 1 2 3 4 5 6
 1 0 1 2 3 4 5
 2 1 1 2 3 4 5
 3 2 2 1 2 3 4
 4 3 3 2 2 3 4
 5 4 4 3 3 2 3
 6 5 5 4 4 3 2

The LCS has length $3$ (the program finds DNI; DAC is another one: the LCS is not unique). The edit distance is $2$: replace $\text{P}$ by $\text{T}$ and $\text{I}$ by $\text{O}$. Step through the two tables; in each step the grammar highlights the case of the recurrence that is used and the explanation gives the three numbers compared.

Relations. If only insertions and deletions are allowed, the distance is $m + n - 2 \cdot \text{LCS}$ (checked on random strings). The longest palindromic subsequence of a string is the LCS of the string and its reverse.

0/1 knapsack

Let $K[i][c]$ be the best value that can be obtained from the first $i$ items with capacity $c$. Item $i$ is either left (value $K[i-1][c]$) or, if it fits, taken (value $v_i$ plus the best for the remaining capacity):

$K[i][c] = \begin{cases} 0 & i = 0,\\ K[i-1][c] & w_i > c,\\ \max\bigl(K[i-1][c],\ v_i + K[i-1][c - w_i]\bigr) & w_i \le c. \end{cases}$

Time and space $\Theta(nW)$. Capacity $W$ is a number: the time is polynomial in its value but exponential in its length in bits, so this is a pseudo-polynomial algorithm (the problem is NP-hard, no polynomial algorithm is known). The table can be reduced to one row of $W + 1$ entries by processing the capacities from $W$ down to $w_i$ (so that the entry $c - w_i$ still holds the value of the previous item); space $\Theta(W)$ when only the value is needed. The set of items is recovered by walking back: item $i$ is taken exactly when $K[i][c] \ne K[i-1][c]$.

The table for items $(w, v) = (3, 30), (4, 50), (2, 15), (5, 60)$ and capacity $8$:

The best value is $90$ (items $1$ and $4$, weight $3 + 5 = 8$). The greedy rule of the fractional knapsack (best value per weight first, taking whole items) would take item $2$ (ratio $12.5$), then item $1$ (ratio $10$) and reach only $80$: the greedy rule fails for the 0/1 problem, DP does not (greedy knapsack).

Matrix chain multiplication

The number of ways to bracket $n$ matrices is the Catalan number $C_{n-1} = \frac{1}{n}\binom{2n-2}{n-1}$: $1, 1, 2, 5, 14, 42, \ldots$ for $n = 1, 2, 3, 4, 5, 6, \ldots$ (the DP never lists them). Let $m[i][j]$ be the fewest scalar multiplications for $A_i \cdots A_j$. The last multiplication splits the chain after some $k$ ($i \le k < j$): multiply $A_i \cdots A_k$ (a $p_{i-1} \times p_k$ matrix) by $A_{k+1} \cdots A_j$ (a $p_k \times p_j$ matrix):

$m[i][j] = \begin{cases} 0 & i = j,\\ \min_{i \le k < j}\ \bigl(m[i][k] + m[k+1][j] + p_{i-1}\, p_k\, p_j\bigr) & i < j. \end{cases}$

The table is filled by increasing chain length $j - i$, because the entries on the right use shorter chains. There are $\Theta(n^2)$ states and each takes $O(n)$ time: time $\Theta(n^3)$, space $\Theta(n^2)$; exactly $(n^3 - n)/6$ split points are examined in total. Keeping the best $k$ in a second table $s[i][j]$ gives the bracketing.

The program computes the knapsack and the chain $A_1 (5 \times 12), A_2 (12 \times 4), A_3 (4 \times 20), A_4 (20 \times 8), A_5 (8 \times 10)$.

#include <stdio.h>
 
static int max(int a, int b) { return a > b ? a : b; }
 
int main(void) {
    /* 0/1 knapsack: items 1..4, capacity 8 */
    int w[5] = {0, 3, 4, 2, 5}, v[5] = {0, 30, 50, 15, 60}, W = 8;
    int K[5][9];                                         /* K[i][c] = best value using only the first i items with capacity c */
    for (int i = 0; i <= 4; i++) {
        for (int c = 0; c <= W; c++) {
            if (i == 0) K[i][c] = 0;
            else if (w[i] > c) K[i][c] = K[i - 1][c];
            else K[i][c] = max(K[i - 1][c], v[i] + K[i - 1][c - w[i]]);
        }
    }
    printf("knapsack: best value %d, items taken:", K[4][W]);
    for (int i = 4, c = W; i > 0; i--)
        if (K[i][c] != K[i - 1][c]) { printf(" %d", i); c -= w[i]; }
    printf("\n");
 
    /* matrix chain: A1 is 5x12, A2 is 12x4, A3 is 4x20, A4 is 20x8, A5 is 8x10 */
    int p[6] = {5, 12, 4, 20, 8, 10}, n = 5;
    long m[6][6];                                        /* m[i][j] = fewest scalar multiplications for A_i ... A_j */
    int s[6][6];                                         /* s[i][j] = the best place k to split */
    for (int i = 1; i <= n; i++) m[i][i] = 0;
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            m[i][j] = 1L << 40;
            for (int k = i; k < j; k++) {
                long cost = m[i][k] + m[k + 1][j] + (long)p[i - 1] * p[k] * p[j];
                if (cost < m[i][j]) { m[i][j] = cost; s[i][j] = k; }
            }
        }
    }
    printf("matrix chain: fewest multiplications %ld\n", m[1][n]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j < i) printf("%6s", ".");
            else printf("%6ld", m[i][j]);
        }
        printf("\n");
    }
    return 0;
}

knapsack: best value 90, items taken: 4 1
matrix chain: fewest multiplications 1400
     0   240   640  1040  1400
     .     0   960  1024  1440
     .     .     0   640   960
     .     .     .     0  1600
     .     .     .     .     0

The cheapest bracketing is $((A_1 A_2)((A_3 A_4) A_5))$ with $1400$ scalar multiplications; multiplying from left to right, $(((A_1 A_2) A_3) A_4) A_5$, costs $1840$. In the animation the explanation of each cell lists every split point it tries and marks the best one.

Worked examples

Cheat box

Traps and GATE patterns

Connections

All four use the recipe of dynamic programming. The 0/1 knapsack contrasts with the greedy fractional knapsack (activity selection and fractional knapsack). Sequence DP of the same kind is in LIS and coin change, and the interval-style table (matrix chain) has a cousin in the shortest-path table of Floyd-Warshall.

PYQs

Define Rn to be the maximum amount earned by
cutting a rod of length n meters into one or more
pieces of integer length and selling them. For i >
0, let p[i] denote the selling prices of a rod whose
length is i meters. Consider the array of prices :
p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10,
p[6] = 17, p[7] = 18

Which of the following statements is/are correct
about R 7 ?

Assume that multiplying a matrix G 1 of
dimension p×q with another matrix G 2 of
dimension q × r requires scalar multiplications.
Computing the product of matrices
G1 G2 G3 ......Gn can be done by
parenthesizing in different ways. Define Gi
Gi+1 as an explicitly computed pair for a given
parenthesization if they are directly multiplied.
For example, in the matrix multiplication chain
G1 G2 G3 G4 G5 G6 using parenthesization
ALGORITHMS

Check Out Our Gate Courses & Secure Your Dream Rank !

(G1(G2G3)) (G4(G5G6)).G2 G3 and G5 G6 are
the only explicitly computed pairs. Consider a
matrix multiplication chain F1 F2 F3 F4 F5 ,
where matrices F1 F2 F3 F4 F5 are of
dimensions 2 × 25, 25 × 3, 3 × 16, 16 × 1 and
1×1000, respectively.In the parenthesization of
F1 F2 F3 F4 F5 that minimizes the total number
of
scalar
multiplications,
the
explicitly
computed pairs is/are:

Consider the weights and values of items listed
below. Note that there is only one unit of each item.
The task is to pick a subset of these items such that
their total weight is no more than 11 Kgs and their
total value is maximized. Moreover, no item may be
split. The total value of items picked by an optimal
algorithm is denoted by Vopt. A greedy algorithm
sorts the items by their value-to-weight ratios in
descending order and packs them greedily, starting
from the first item in the ordered list. The total value
of items picked by the greedy algorithm is denoted
by Vgreedy.
The value of Vopt - Vgreedy is

Let A 1 , A 2 , A 3 , and A 4 be four matrices of
dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5,
respectively. The minimum number of scalar
multiplications required to find the product
A1A2A3A4
using
the
basic
matrix
multiplication method is   .

Four matrices M1, M2, M3 and M4 of
dimensions pxq, qxr, rxs and sxt respectively
can be multiplied is several ways with different
number of total scalar multiplications. For
example, when multiplied as ((M1 X M2) X (M3
X M4)), the total number of multiplications is
pqr + rst + prt. If p = 10, q = 100, r = 20, s = 5
and t = 80, then the number of scalar
multiplications needed is:
ALGORITHMS

Check Out Our Gate Courses & Secure Your Dream Rank !

The subset-sum problem is defined as follows.
Given
a
set
of
n
positive
integers,
S={a1,a2,...,an} and positive integer W, is there
a subset of S whose elements sum to W? A
dynamic program for solving this problem uses
a 2-dimensional Boolean array, X, with n rows
and W+1 columns. X[i,j], 1≤i≤n, 0≤j≤W, is
TRUE if and only if there is a subset of
{a1,a2,...,ai }whose elements sum to j.
Which entry of the array X, if TRUE, implies
that there is a subset whose elements sum to W?

The subset-sum problem is defined as follows.
Given a set of n positive integers, S={a1,a2,...,an
} and positive integer W, is there a subset of S
whose elements sum to W? A dynamic program
for solving this problem uses a 2-dimensional
Boolean array, X, with n rows and W+1
columns. X[i,j], 1≤i≤n, 0≤j≤W, is TRUE if and
only if there is a subset of {a1,a2,...,ai }whose
elements sum to j.Which of the following is
valid for 2≤i≤n and ai≤j≤W?

Self-check

Revision card

References