= Ordered word concatenation dynamic programming
Given ordered words $w_1,\ldots,w_n$ and a target $s$, minimise the number of words in an order-preserving <subsequence> whose <concatenation> is $s$. Let $D(i,j)$ be the optimum using the first $i$ words to produce the first $j$ symbols. Either skip $w_i$, or, when it matches the target suffix ending at $j$, take it and add one to $D(i-1,j-|w_i|)$. The state records both the available-word boundary and target progress, preventing reuse or reordering of words. For $|s|=O(n)$ and bounded word length, this is an $O(n^2)$-time algorithm with straightforward predecessor reconstruction.
Back to article page
