 tried coding it http://ideone.com/eYeKnd
practice problem CB03

It’s a basic dynamic programming question. Starting with very basic, for dp to be applicable, we need two things to be satisfied: Overlapping subproblems and Optimal substructure.

Optimal Substructure
: Lets say we need to find the number of palindromic subsequences in range (i,j). If s[i]==s[j], then we need to count all possible combinations of subsequences in the range (i+1,j-1) with i and j. Ex: if the string is

``````    0 1 2 3 4
a b c b a
``````

Here s== s, so if we include the subsequence formed by concatenation of s+(bcb)+s, it needs to be counted. Thus, if we know the optimal solution to problem (i+1,j-1), we can find optimal solution to problem (i,j). Hence, this property is satisfied.

Overlapping subproblems :
Doing like above, to count, we count subsequences in the interval [i,j], [i+1,j] and [i,j-1]. These subproblems can anytime overlap. Ex:

``````        [0,4]
/   \  // Please see I didn't took the third possibility of range [i+1,j-1]
/     \       // just for better visibility and understandability. You can take and
[0,3]     [1,4]     // draw the recursion tree
/   \      /  \
[0,2] [1,3][2,4] [1,3] // Notice the overlap of subproblem [1,3] here.
``````

Thus, the two properties are satisfied and we can now apply dp. Let us make a 2-d array a[i][j] which denotes the number of palindromic subsequences in the range [i,j]. Thus a[i][i]=1 for all 1<=i<=n. For the range [i,j] we have two cases.

• If s[i]== s[j]
• If s[i]!=s[j]

Let’s talk about the second case when s[i] is not equal to s[j], then we need the count of subsequences:

• those which contain S[i] but not S[j]
• Those which contain S[j[ but not S[i]
• Those which don’t contain either of them

Th only thing to notice here is that, a[i][j-1] includes first and third case of the above list. ALso, a[i+1][j] includes second and third case f the above list. I.e. a[i+1][j-1] this count is included twice. Hence,

``````a[i][j]= a[i+1][j] + a[i][j-1]+ a[i+1][j-1];
``````

Talking about the case when s[i]==s[j], we can see that we have to add the palindromes consisting of s[i] followed by a subsequence palindrome from S[i+1,j-1] followed by S[j], as well as the palindromic subsequence consisting of just the start(a[i][j-1]) and end characters(a[i+1][j]).
Thus,

``````we already had :
a[i][j]= a[i][j-1] + a[i+1][j] -a[i+1][j-1]
We now need to add a[i+1][j-1] +1, ex subsequence : "a s(i+1,j-1) a then adding 1 for the subsequence (a,a)
a[i][j] = a[i][j-1]+ a[i+1][j] - a[i+1][j-1] + a[i+1][j-1]+1;
a[i][j] = a[i][j-1]+ a[i+1][j] +1;
``````

Thus recursion follows this manner:

``````void count(int low, int high, char str[])
{
if(low>high) return 0;
if(low==high) return 1;
if(str[low]==str[high])
return count(low,high-1,str) + count(low+1,high,str) - count(low+1,high-1,str);
else
return count(low,high-1,str) + count(low+1,high,str) +1;
}
``````

Now, you can see in the above code, many subproblems will be computed again and again. Adding memoization to it:

``````int count(int low, int high, char str[])
{
if(low>high)
return 0;

if(low==high)
return 1;

if(a[low][high]!=-1)
return a[low][high];
else{
a[low+1][high] = count(low+1,high,str);
a[low][high-1]= count(low,high-1,str);
}
int p = a[low+1][high] + a[low][high-1];

if(str[low]!=str[high])
return  p- count(low+1,high-1,str);
else
return p +1;
``````

}

Hope it clears 2 Likes

The only thing to notice here is that a[i][j-1] includes the first and third case of the above list. Also, a[i+1][j] includes second and third case f the above list. I.e. a[i+1][j-1] this count is included twice. Hence,

``````a[i][j]= a[i+1][j] + a[i][j-1] - a[i+1][j-1];
``````

Typo in the above statement

//