CB03 practice(peer) explanation please

tried coding it http://ideone.com/eYeKnd
please someone explain
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[0]== s[4], so if we include the subsequence formed by concatenation of s[0]+(bcb)+s[4], 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 :slight_smile:

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