here is a pseudo code for counting all palindromic subsequence of a given string :
enter code here
if i == j
return 1
Else if (str[i] == str[j)]
return countPS(i+1, j) + countPS(i, j-1) + 1;
else
return countPS(i+1, j) + countPS(i, j-1) - countPS(i+1, j-1)
i couldn’t understand that , when first and last characters are equal why we do not subtract -countPS(i+1, j-1)
as we did when when 1st and last are not same. ?
source : https://www.geeksforgeeks.org/count-palindromic-subsequence-given-string/
Can anyone please explain it ?