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
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