# Proving optimality of a dynamic programming algorithm

We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ reversed. In other words, we're choosing some even-length palindrome and erasing it's "right half".

The goal is to minimize the length of the word left when no further can moves be done. In example, from a bit word $100110$ we can erase $01$ from the middle, and be left with $1010$ where no moves can be done. However, starting differently, we can reduce the word to a single $10$, which is optimal. I want to compute this minimal length for a given string, for $100110$ it would be $2$.

Now, I have a dynamic-programming algorithm which I know produces right answers (it has been tested a lot), but don't know how to prove it. It computes the best result for every substring of $s$ in increasing length. For those of length $k$, the answer is surely at most $k$. Also, it's obvious that the only strings in which no moves can be done are of form $1010...$ or $0101...$. For some word we're playing on, as it's first bit can never be erased, we know the exact form of a word that will be left from it, the only thing that we lack is it's length. Now, I assumed that for a word $t$, there exist some words $x$, $y$ that $t = xy$, and if we do the optimal operations just on $x$, producing a word $x'$, then just on $y$ producing $y'$, and in the end on the word $x' y'$, we will acquire the optimal result for $t$. The last step is very easy, because we know how words $x'$ and $y'$ look like only knowing it's lengths, so there are only a couple of cases to consider. The complexity of this process is $O(n^3)$ as it spends linear time on each substring of $s$.

If $DP[i][j]$ is the answer for a substring $[i..j]$, the complete recurrence is as follows:

$$DP[i][j] = \min \{DP[i][k] + F(i,k,j) \cdot DP[k+1][j] : i \leq k < j \}.$$

where

$$F(i,k,j) = \left\{ \begin{array}{ll} 1 & \textrm{for s[i] = s[k+1] and DP[i][k] = 1}\\ 1 - DP[i][k] \mod 2 & \textrm{for s[i] = s[k+1] and DP[i][k] > 1}\\ DP[i][k] \mod 2 & \textrm{otherwise} \end{array} \right.$$

what corresponds to the fact that in some cases $y'$ can be erased using $x'$ (possibly in multiple moves) - in those cases $F(i,k,j)$ is $0$, and it's $1$ otherwise. Also note, that if $s[i] = s[i+1]$ then when dealing with $DP[i][j]$ for $j > i$ at first we initialize $DP[i][j] = DP[i+1][j]$.

For me, the assumption that $t$ can be split into $x$ and $y$ in a such a way that the mentioned procedure is optimal, is non-trivial. I'm asking for a proof that this assumption can be made, or some different solutions for this problem, either would be nice.

• "which I know produces right answers (it has been tested a lot)" -- Uhhhh... Regarding proof strategies, see here. What's your recurrence? – Raphael Sep 22 '14 at 17:54
• This problem is from an old contest, and it has passed the tests, so basically it passes all cases the problem author could come up with, what convinced me of it being correct... – Cris Sep 22 '14 at 18:02
• If I drove your car around the block once and proclaimed it was sound and safe, would you take my word for it? – Raphael Sep 22 '14 at 18:05
• Passing the tests made up for this problem by contest authors is perhaps more comparable to having this car thoroughly tested for safety by experts, that had an interest in proving it unsafe. But I get your point though, that's why I'm interested in a formal proof. – Cris Sep 22 '14 at 18:26
• It will be nice if you share with us the source of problem or links of the problem contest. I'd like to read all about the problem and review test cases, for example. – jonaprieto Sep 23 '14 at 2:32

Since you're asking how to construct a proof of correctness, I'll give you some tips to get you started. If you do all of these, I think you'll be able to make a lot more progress.

1. As Raphael suggests, make that you can write a recurrence relation for the solution. You don't yet have a recurrence. A recurrence is an equation for $DP[i][j]$ that is written solely in terms of $i,j,s$ and other "earlier" values of $DP[\cdot][\cdot]$. Your equation involves a variable $k$, but what is $k$? Where'd that come from? It comes out of the blue. How do we choose $k$? You haven't yet given us a formula that computes $DP[i][j]$. Until you do that, you can't possibly hope to prove your algorithm correct. In fact, until you do that, you don't even have an algorithm!

Hint: I think you'll find you want to write something like

$$DP[i][j] = \min \{...\text{something}... : k=i-1,i,i+1,\ldots,j-1\}.$$

You fill in the $\text{something}$ part. In short, I recommend that you formulate your recurrence more accurately.

Hint: try writing out the pseudocode for your dynamic programming algorithm, in standard form. This will force you to write a recurrence for $DP[i][j]$.

2. Once you have a recurrence, your next step is to prove that it is correct. Why does it give the correct answer for your problem? Justify why the recurrence is correct. Here you might use proof by induction.

See Raphael's answer, which gives an excellent overview for how to prove a dynamic programming algorithm correct.

I recommend that you review the proof of correctness for a few other dynamic programming algorithms. (Look in a few standard algorithms textbooks; with any luck, they should show you several examples.) You'll see that they have a similar structure, and this should help you structure your proof.

3. One more tip that will be very helpful. You write "I assume (...)". You might try proving that the "(...)" statement is true.

• I do have an algorithm, as well as I have it implemented. Just looking at the recurrence does no help, because it's being correct solely depends on the assumption I made. Things you gave me are vague ideas, what would actually help is some starting point for this specific problem, such as "let's take some optimal sequence of moves on string $s$, WLOG we can assume that the last move is... / there exists a position such that..." etc. – Cris Sep 23 '14 at 10:11
• @Cris The heart of the problem is part (3). Make a stab at proving (or refuting) it yourself. It may be "non-trivial", as you mention, but that just means that you have to think a bit. – Yuval Filmus Sep 23 '14 at 13:24
• @Cris, As Yuval says, part (3) is the most essential part. But that doesn't mean you can neglect the rest. You should still write down the recurrence carefully. It's a prerequisite to having a proof. It might be the easy part; if so, do it, then go focus on the hard part. But leaving it out of your question makes it impossible for us to give you feedback on that part, and might cause you to head in an entirely wrong direction (if you're not able to formulate the recurrence properly). – D.W. Sep 23 '14 at 16:43