What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?
Go over all $2^n$ subsequences. For each one, check whether it is increasing.
There are two meanings of subsequence: contiguous subsequence and arbitrary subsequence. For example, $1,3$ is a non-contiguous subsequence of $1,2,3$.
Formally, a subsequence of $a_1,\ldots,a_n$ is a sequence $a_{i_1},\ldots,a_{i_m}$ for some $1 \leq m \leq n$, where $1 \leq i_1 &lt; \cdots &lt; i_m \leq n$. A subsequence is contiguous if it is of the form $a_i,a_{i+1},\ldots,a_j$, that is, if it contains all elements from $a_i$ to $a_j$.
A sequence of length $n$ has $2^n-1$ subsequences, only $\binom{n+1}{2}$ of which are contiguous.
For example, here are all subsequences of $a,b,c$:
$$
a \\ b \\ c \\ a,b \\ a,c \\ b,c \\ a,b,c
$$
Of these, only $a,c$ is not contiguous.