Proving optimality of a dynamic programming algorithm
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.


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]$.
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.
One more tip that will be very helpful.  You write "I assume (...)".  You might try proving that the "(...)" statement is true.