Can some one write a better editorial for COUNTPAL .A bit in detail for novice programmer like me.
Thanks before hand
Notation: we’ve got string s, and s[i] is character on i-th position. First character is on position 0, second on position 1 and so on. Total length of string is n, so last letter is s[n-1].
So first thing is dynamic programming itself. Denote F(i) number of different ways you can create substring s[0]s[1]…s[i-1] from only palindromes. Obviously the F(n) is result for our problem, because it’s number of ways for substring s[0]…s[n-1] so whole string s.
Now on the end of our substring s[0]…s[i] must be palindrome and we can tear off this palindrome. We try each position j and if substring s[j]…s[i-1] creates palindrome, than we can rip off this segment and we end up with substring s[0]…s[j-1]. This substring has F(j) ways to disintegrate, so we add to total number of ways in F(i) value F(j).
In other words, F(j) can be computed as sum of all F(j) when substring s[j]…s[i-1] creates palindrome.
int F(int i) {
if(i==0) return 1;
int res=0;
for(int j=0; j<i; j++)
if(substring s[j]...s[i-1] is palindrome) res+=F(j);
return res;
}
Here is simple pseudocode to this function. Of course, if you want it fast enough, you must use memoization and each F(i) compute at most once. But without is clearer.
Last thing is, how we find out if some substring s[j]…s[i-1] is palindrome. This we can simply precompute or can be computed by the time. The smallest palindromes are with zero characters and one character, so for s[i]s[i-1] (notice that there is no character in this substring, because i>i-1) and s[i-1] is answer yes. Larger substring can be compute easily. If we get substring s[j]…s[i-1] than s[j] must be equal as s[i-1] and substring s[j+1]…s[i-2] must be palindrome.
Again simple pseudocode:
bool isPalindrome(int j, int i) {
if(j==i || j+1==i) return true; //if substring is empty or contain one character
if(s[j]!=s[i-1]) return false; //if first and last letters are different return false
return isPalindrome(j+1, i-1);//first and last letters are equal, so return true if s[j+1]...s[i-2] is palindrome
}
I hope, that you now understand solutions for this problem and have no problem in understanding c++ pseudocodes. Don’t forget to use memoization in both function. Than you obtain time complexity O(n^2). If you’ve got any question, just ask 
And to complete this solutions, here is my whole correct implementation in C++.
1 Like
#include < iostream >
#include< algorithm >
#include< string >
using namespace std;
string s;
bool isPallindrome(int j, int i)
{
if(j==i || j>i) return true;
if(s[j]!=s[i-1]) return false;
return isPallindrome(j+1, i-1);
}
int F(int i) {
if(i==0) return 0;
int res=0;
for(int j=0; j < i; j++)
if(isPallindrome(j,i))
{res++;F(j);}
return res;
}
int main()
{
int calc=0;
cin>>s;
for(int i=1;i < s.size();i++)
calc+=F(i);
cout<< calc;
return 0;
}
whats wrong in this?
Actually for
input
bobseesanna
output
18
but this code gives
output
14
So whats wrong in this ?
Thanks,for such a nice description,i will code it and will ask if i face any more trouble… 
One more foolish doubt i guess. As you have explained in your above
int F(int); function… res+=F(j) how is res getting updated…
sadly I don’t understand what “res getting updated” supposed to mean. You just compute it in function and that’s all. Of course, don’t forget to module it everytime.
“…don’t forget to module it everytime” (WA) and of course you can add some caching to prevent TLE…
If i change the loop inside main to for(int i=1;i<=s.size();i++) its giving 16 as output for input bobseesanna
ok, two mistakes are yours, one mine (sorry)
Mine mistake: F(0)=1 not 0 as I’ve got in pseudocode
Yours: you want to compute value F(s.length()) so get rid off that for cycle in main and just do cout << F(s.length()) << endl;
Second, I don’t understand how you get res++;F(j); but correctly it should be res+=F(j);
if you don’t know c++ syntax it’s same as res=res+F(j);
Ok got it F(0)=1 was the key…thank u
yes, sorry for confusing