dp[i] = lets partition it till i-1
for (int l = 0; l < n; ++l)
for (int r = 1; r <= n; ++r)
dp[r] = min(dp[r], dp[l] — (r != n? lcp(a[l], a[r]): 0) + |a[l]| + |a[l + 1]| + ... + |a[r — 1]| — f(a[l], a[l + 1]) — f(a[l+1], a[l+2]).... f(a[r — 2], a[r — 1) (this can be found with partial sum));

First, some notation. We have binary strings s₁... s_n each of length k. Let s_i(l) denote the prefix of s_i of length l.

Now, let dp[x][suf] be the minimum cost for strings s₁... s_x given that one subsequence ends in s_x and the other ends in suf. Note that suf can have length between 0 and k. Our state transition is:

Here is the logic behind the transition. In order to make two subsequences, one ending with s_x and the other in suf, we can either append s_x to the subsequence ending with s_x - 1, or we can append s_x to a subsequence ending in s_x(l) where 0 ≤ l ≤ k. In the later case, we will end up with one subsequence ending with s_x and the other subsequence ending with s_x - 1, so we need only evaluate this case if s_x - 1 ends in suf.

I'll let you figure out the details of the implementation as an exercise. You'll need to figure out how to handle state transitions in an efficient manner.