Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 6 / c

Let $m=|s|$, ${\ell }_i=|w_i|$, and let $D(i,j)$ be the minimum number of words chosen from $w_1,\dots ,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 areFor $i\ge 1$,Here $s[a:b]$ denotes indices $a,\dots ,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 $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 three words, indices $(2,5,6)$, whose concatenation is 010111. This is ordered word concatenation dynamic programming.