素DNAの長さの上限を $L \leq 20$ とします。また、合成したいDNA鎖を表す文字列を $S$ とし、この長さを $sz$ とします。 $sz=1$ の場合は明らかに答えは $1$ です。そうでない場合を考えます。
$dp[i]$ を $S$ の先頭 $i$ 文字目までからなる文字列を作るために必要な個数とします。 $dp[0]=0$ であり、求めるものは $dp[sz]$ です。

$dp[i]$ を求める方法を考えます。 $i$ 文字目が一番最後とする素DNAの長さを $j$ と決め打つとき、 $S$ の $i-j+1$ 文字目から $i$ 文字目からなる $j$ 文字の部分文字列が素DNAにあればいいです。このような $j$ が存在しない場合、 $dp[i] = \infty$ です。
この時、 $dp[i]= \min \left( dp[i-j+1],dp[i-j+2], \cdots , dp[i-1] \right) + 1$ となります。
$j > L$ については考慮する必要がなく、遷移の式より $j$ が部分文字列が素DNAにあるようなものの中で最大のもののみを考えて構いません。よって遷移は $O(L)$ となり、部分文字列があるかの検索を除いて、この問題は $O(szL)$ で解くことができます。

部分文字列が素DNAにあるかを判定する方法ですが、 ATGC をそれぞれ数字の \(1,2,3,4\) とし、文字列を \(5\) 進数の数字ととらえた後、この数字を用いたsetを前準備で用意するなどがあります。
文字列のままsetにいれたり、mapを利用するのはメモリや時間制限の点で効率が悪いので気を付けましょう。