Problem $7$: Dynamic Programming

The following problem can be useful for data compression. The input is a string s of length n and a list of $k$ strings $x_1,$dots,$x_k$ of lengths $m_1,$dots,$m_k$ respectively. The problem is to determine the smallest number of copies of strings from $x_1,$dots,$x_k$ that can be concatenated together to produce s$.($you can use as few or as many copies of each string as you want$)$

For example, if $S=$bababbababa,$x_1=a,x_2=ba,x_3=$abab, and $x_4=b,$ then we can write $s=x_4{x}_3{x}_2{x}_3{x}_1$ which is optimal, so the answer is $5.$

$($a$)$ For $i0,$ let Opt$(i)$ be the optimal number of strings required to produce the string $s[1$:$i],$ meaning the prefix of $s$ of length $i.$ Describe a recursive algorithm for computing Opt$($n$).$ Don't forget the base case.

$($b$)$ Describe how you can compute Opt$($n$)$ efficiently without recursion, using a dynamic programming algorithm.

$($c$)$ Let $m$ be the maximum for $m_i$ for all $i.$ What is the running time of your algorithm in terms of $n,k$ and m $?$