= Solution
Let $m=|s|$, $\ell_i=|w_i|$, and let $D(i,j)$ be the minimum number of words chosen from $w_1,\ldots,w_i$, in their given order, whose <concatenation> equals the length-$j$ <prefix of a list> of $s$. Use $\infty$ for impossibility. The boundary values are
$$
D(0,0)=0,\qquad D(0,j)=\infty\quad(j>0).
$$
For $i\geq1$,
$$
D(i,j)=\min\left\{
D(i-1,j),\quad
1+D(i-1,j-\ell_i)\ \text{if }j\geq\ell_i\text{ and }s[j-\ell_i:j]=w_i
\right\}.
$$
Here $s[a:b]$ denotes indices $a,\ldots,b-1$. The first case omits $w_i$. In the second, the last selected word is $w_i$, so removing it leaves a solution using only earlier words for the shorter prefix. These are exhaustive alternatives. Conversely either alternative constructs a valid solution, proving the <dynamic programming> recurrence. Even an empty word causes no cycle because both alternatives use row $i-1$.
Fill rows in increasing $i$ and store the chosen alternative for every finite entry. If $D(n,m)=\infty$, report no solution. Otherwise trace back from $(n,m)$: a skip moves to $(i-1,j)$; a take records index $i$ and moves to $(i-1,j-\ell_i)$. Reverse the recorded indices to obtain the required <subsequence>. Ties may choose either valid predecessor.
There are $(n+1)(m+1)$ states. A substring comparison costs $O(\ell_i)$, so under the given bounds $m=O(n)$ and $\ell_i=O(1)$ the running time is \b[$O(n^2)$], with $O(n^2)$ storage including reconstruction choices. Two rows give $O(m)$ working storage if only the optimum count is needed. For the source example, the optimum is \b[three words, indices $(2,5,6)$], whose concatenation is `010111`. This is <ordered word concatenation dynamic programming>.
Back to article page
