DP on sequences: LIS and coin change

Why it exists

Many optimisation problems are about one sequence: pick the longest increasing run from a list, pay an amount with as few coins as possible. They are the simplest dynamic programs, with a one-dimensional table, and each teaches something specific: LIS shows how a DP can be sped up from $n^2$ to $n \log n$ with a cleverly chosen quantity, and coin change shows how the order of the loops changes what is being counted and why a greedy rule that works for ordinary money fails for other coin systems.

Prerequisites

You need the dynamic programming recipe (dynamic programming) and binary search (binary search).

Precise definitions

Increasing subsequence. Positions $i_1 < i_2 < \cdots < i_k$ with $a_{i_1} < a_{i_2} < \cdots < a_{i_k}$ (strictly; non-decreasing uses $\le$). The longest increasing subsequence (LIS) has the largest $k$. It need not be unique and it need not be contiguous.

Coin change, fewest coins. Coin values $c_1, \ldots, c_k$ (unlimited supply of each) and an amount $T$; find the fewest coins whose values sum to $T$ (or report that it is impossible).

Coin change, number of ways. The number of different combinations of coins (the order of the coins does not matter: $1 + 3$ and $3 + 1$ are one way) with sum $T$. If order matters the count is of sequences (compositions).

How it works

LIS: the quadratic dynamic program

Let $L[i]$ be the length of the longest increasing subsequence that ends at position $i$. It is one more than the best $L[j]$ over the earlier positions $j < i$ whose value is smaller: $L[i] = 1 + \max\{\, L[j] : j < i,\ a_j < a_i \,\}\quad (\max \emptyset = 0), \qquad \text{answer} = \max_i L[i].$ Note the definition: $L[i]$ is not "the LIS of the first $i$ elements" (that is the prefix maximum of $L$). Time $\Theta(n^2)$ (each $i$ looks at all $j < i$), space $\Theta(n)$. Storing the position $j$ that gave the maximum allows the subsequence to be printed by following these links back from the best $i$.

The program below computes both the LIS and the coin tables for the array $8, 3, 7, 4, 10, 5, 12, 6, 11, 9$.

#include <stdio.h>
 
int main(void) {
    int a[10] = {8, 3, 7, 4, 10, 5, 12, 6, 11, 9}, n = 10;
    int L[10], parent[10];                               /* L[i] = length of the longest increasing subsequence that ENDS at a[i] */
    int best = 0, last = 0;
    for (int i = 0; i < n; i++) {
        L[i] = 1;
        parent[i] = -1;
        for (int j = 0; j < i; j++)
            if (a[j] < a[i] && L[j] + 1 > L[i]) { L[i] = L[j] + 1; parent[i] = j; }
        if (L[i] > best) { best = L[i]; last = i; }
    }
    printf("LIS length %d:", best);
    int seq[10], k = best;
    for (int i = last; i >= 0; i = parent[i]) seq[--k] = a[i];
    for (int i = 0; i < best; i++) printf(" %d", seq[i]);
    printf("\n");
 
    int tails[10], size = 0;                             /* tails[l] = smallest possible last element of an increasing subsequence of length l + 1 */
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] < a[i]) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = a[i];
        if (lo == size) size++;
    }
    printf("tails method: length %d\n", size);
 
    int coins[3] = {1, 3, 4}, T = 12;
    int fewest[13], ways[13];                            /* fewest coins, and the number of different sets of coins, that make each amount */
    fewest[0] = 0;
    ways[0] = 1;
    for (int x = 1; x <= T; x++) { fewest[x] = 1 << 20; ways[x] = 0; }
    for (int x = 1; x <= T; x++)
        for (int c = 0; c < 3; c++)
            if (coins[c] <= x && fewest[x - coins[c]] + 1 < fewest[x]) fewest[x] = fewest[x - coins[c]] + 1;
    for (int c = 0; c < 3; c++)
        for (int x = coins[c]; x <= T; x++) ways[x] += ways[x - coins[c]];
    printf("amount:");
    for (int x = 0; x <= T; x++) printf(" %2d", x);
    printf("\nfewest:");
    for (int x = 0; x <= T; x++) printf(" %2d", fewest[x]);
    printf("\nways:  ");
    for (int x = 0; x <= T; x++) printf(" %2d", ways[x]);
    printf("\n");
    return 0;
}

LIS length 5: 3 4 5 6 11
tails method: length 5
amount:  0  1  2  3  4  5  6  7  8  9 10 11 12
fewest:  0  1  2  1  1  2  2  2  2  3  3  3  3
ways:    1  1  1  2  3  3  4  5  6  7  8  9 11

The LIS has length $5$, for example $3, 4, 5, 6, 11$ (another is $3, 4, 5, 6, 9$): not unique.

LIS in $O(n \log n)$: the tails array

Keep an array $\text{tails}$ in which $\text{tails}[l]$ is the smallest possible last element of an increasing subsequence of length $l + 1$ among the elements seen so far. This array is always increasing (a smaller tail exists for shorter subsequences). For each new element $x$: binary-search the first tail that is not smaller than $x$ and replace it by $x$; if every tail is smaller than $x$, append $x$ (the longest subsequence has grown). The length of the LIS is the final size of the array. Each element costs one binary search: time $\Theta(n \log n)$, space $\Theta(n)$.

Why it is right: replacing a tail by a smaller value keeps the same length but makes the subsequence easier to extend later, and appending happens exactly when $x$ extends the longest one. (The array $\text{tails}$ itself is not in general an increasing subsequence of the input, only its size is the answer; to print the sequence you store, for every element, the position of the tail before it.)

For non-decreasing subsequences the search is for the first tail strictly larger than $x$.

Coin change

Fewest coins. Let $f(x)$ be the fewest coins for amount $x$. The last coin has some value $c \le x$, and the rest is an optimal payment of $x - c$: $f(0) = 0,\qquad f(x) = 1 + \min_{c \le x} f(x - c)\quad (x \ge 1).$ With $T$ the amount and $k$ coin values: time $\Theta(kT)$, space $\Theta(T)$. This is the dynamic program that does work for every coin system, where greedy (always take the largest coin) fails for some, such as $\{1, 3, 4\}$ at amount $6$ (greedy method): $f(6) = 2$ ($3 + 3$), while greedy uses $4 + 1 + 1$.

Number of ways (combinations). Let $w(x)$ be the number of multisets of coins with sum $x$. Process one coin value at a time (outer loop over coins, inner loop over amounts): $w(0) = 1;\quad \text{for each coin } c:\ \text{for } x = c, \ldots, T:\ w(x) \mathrel{+}= w(x - c).$ After the coin $c$ has been processed, $w(x)$ counts the combinations using only the coins processed so far. With the loops the other way round (outer loop over amounts, inner over coins) $w(x) = \sum_c w(x - c)$ counts ordered sequences, because any coin may come last.

For the coins $1, 3, 4$ the table shows $f(6) = 2$ and $f(12) = 3$ ($4 + 4 + 4$), and the number of ways to pay $4$ is $3$ ($1 + 1 + 1 + 1$, $1 + 3$, $4$); the number of ordered ways to pay $4$ is $4$ ($1111$, $13$, $31$, $4$).

Relations. Coin change with unlimited coins is the unbounded knapsack (each item may be taken any number of times, value $1$, to be minimised). Deciding whether an amount can be paid at all is the subset-sum style problem with time $\Theta(kT)$, pseudo-polynomial in $T$ like the knapsack (knapsack and others).

Worked examples

Cheat box

Traps and GATE patterns

Connections

Both are instances of dynamic programming with a one-dimensional table; the two-dimensional ones are in LCS, edit distance, knapsack and matrix chain. The coin problem shows where the greedy method fails, and the tails array uses binary search.

PYQs

Consider two strings A = {"qpqrr"} and B =
"pqprqrp". Let x be the length of the longest
common
subsequence
(not
necessarily
contiguous) between A and B and let y be the
number of such longest common subsequences
between A and B. Then x+10y =
.

An algorithm to find the length of the longest
monotonically increasing sequence of numbers
in an array A[0: n - 1] is given below. Let L;
denote the length of the longest monotonically
increasing sequence starting at index i in the
array. Initialize L n-1 = 1. For all i such that 0 ≤
i ≤ n – 2
b) F2 F3 only
L = 1 + Li+1
if A[i] < A[i + 1]
i
{
c) F3 F4 only
d) F1,F2 and F4

The weight of a sequence a0 , a1 , ..., an–1 of real
numbers is defined as a0 + a1 / 2 + ...+ a n–1 /2n–1 .
A subsequence of a sequence is obtained by
deleting some elements from the sequence,
keeping the order of the remaining elements the
same. Let X denote the maximum possible weight
of a subsequence of a0 , a1 ,..., an-1 . Then X is equal
to

A sub-sequence of a given sequence is just the
given sequence with some elements (possibly
none or all) left out. We are given two sequences
X[m] and Y[n] of lengths m and n, respectively,
with indexes of X and Y starting from 0.
We wish to find the length of the longest
common sub-sequence (LCS) of x[m] and Y[n]
as l(m,n), where an incomplete recursive
definition for the function l(i,j) to compute the
length of the LCS of x[m] and Y[n] is given
below:

0, if either i = 0 or j = 0
l(i, j) = { expr1, if i, j > 0 and x [i⁡-⁡1] = Y [j -⁡1]⁡
expr2, if i, j > 0 and x [i - 1] ! = Y [j - 1]
Which one of the following options is correct?

Let A be an array containing integer values. The
distance of A is defined as the minimum number of
elements in A that must be replaced with another
integer so that the resulting array is sorted in non-
decreasing order. The distance of the array [2, 5, 3,
1, 4, 2, 6] is
.

Self-check

Revision card

References