This is a discussion of an Olympiad problem on palindromes in Informatics. 

The problem is stated this way: Some words can be divided into even length palindromes. The word  

aabbaaabbaaa can be divided into 3 even length palindromes.  

aabbaaabbaaa   = aabbaa | abba | aa 

What is the smallest number of even length palindromes in a division of the word: 

(a) aabbaabaabaabbbb? 

(b) aaaaabbaaabbabbabbbb? 

(c) baabbbbaabaabaabbbbb? 

(d) aabbaabaabaabbbbbbbb? 

(e) aaaabbaaabbabbaabbbb? 

Below are the optimal divisions of the words from all subtasks: 

(a) aabbaabaabaabbbb = aa|bbaabaabaabb|bb 

(b) aaaaabbaaabbabbabbbb = aa|aaabbaaa|bbabbabb|bb 

(c) baabbbbaabaabaabbbbb = baab|bbbaabaabaabbb|bb 

(d) aabbaabaabaabbbbbbbb = aa|bbaabaabaabb|bbbbbb 

(e) aaaabbaaabbabbaabbbb = aa|aabbaa|abba|bbaabb|bb 

The given words have the following property: 

If we are looking for prefixes in the given word that are the longest even length palindrome to select as a division, it does not yield the optimal choice 

If we are looking for suffixes in the given word that are the longest even length palindrome to select as a division, it does not yield the optimal choice 

Therefore we cannot apply the greedy strategy. 

Instead we can apply the dynamic programming technique. 

To solve this problem, we apply dynamic programming by following the four-step sequence: 

1.     Characterize the structure of an optimal solution 

2.     Recursively define the value of an optimal solution 

3.     Compute the value of an optimal solution 

4.     Construct an optimal solution from computed information 

In this case we say the optimal structure is as follows: 

The optimal solution for the sequence in the word W (W1,W2,… Wn) is the same as finding the optimal solution of two sub-problems obtained by splitting the range into two involving A1…Ak and Ak+1 .. An and then combining these optimal subproblems. 

In this case we test each partition for the following when combining: 

• Is the left and right division containing only even length palindromes 

The termination condition is when  

• There is a no division and the count at this stage is 0 
• The given word is already an even length palindrome  and the count at this stage is 1 

The progress condition is when palindrome 

• One of the divisions has an even length palindrome 

The optimal solution can be described in a top down recursive strategy as follows: 

Recursive-Even-Length-Palindrome(W, I, j) 

If I == j 

   Return 0 

If IsEvenLengthPalindrome(W,I,j)  

   Return 1 

m[i,j] = infinity 

For k = I to j-1
     leftcost, leftvalid = Recursive-Even-Length-Palindrome(W,I,k)
     rightcost, rightvalid = Recursive-Even-Length-Palindrome(W, k+1, j) 

     q =  leftcost+rightcost 

     If q < m[I,j] 

             M[I,j] = q 

  return m[I,j], leftvalid && rightvalid 

ISEvenLengthPalindrome(W,I,j) = IsPalindrome(W,I,j) && (j-i+1) %2 == 0 

Also the iterations could be optimized by using incrementing k by 2 to j-2 from i since we only consider even lengths. It will require adjusting the termination conditions.