This can be solved by using DP bottom up approach,

1. Initialize dp[n][n] where n be the string length to 0 and a Boolean 2D array pal[n][n] to store whether the substrings are palindrome or not.
2. Fill up the base case,
   Base case is that each single character is a palindrome itself. And for length of two, i.e, if adjacent characters are found to be equal then [i][i+1]=3, pal[i][i+1]=true, else if characters are different then dp[i][i+1]=2, pal[i][i+1]=false
   To understand this lets think of a string like "acaa"
   Here, dp[0][1]=2 because there's only two palindrome possible because of "a" and "c".
   Whereas for dp[2][3] value will be 3 as possible substrings are "a", "a", "aa".

   for i=0 to n
   	// for single length characters
   	dp[i][i]=1;pal[i][i]=true 
   	if(i==n-1)
   		break;        
   	if(s[i]==s[i+1])
   		dp[i][i+1]=3;,pal[i][i+1]=true
   	else
   		dp[i][i+1]=2,pal[i][i+1]=false;
   	end if
   end for
   

3. Compute for higher lengths,

   for len=3 to n
   	for start=0 to n-len
   		int end=start+len-1;
   		// start and end is matching and rest of 
   		// substring is already palindrome
   		if(s[end]==s[start]  and pal[start+1][end-1]) 
   			// 1+subsequence from semaining part
   			dp[start][end]=1+dp[start+1][end]+dp[start][end-1]-dp[start+1][end-1]; 
   			Pal[start][end]=true;
   		else
   			dp[start][end]=dp[start+1][end]+dp[start][end-1]-dp[start+1][end-1];
   			Pal[start][end]=false;
   		end if
   	end for
   end for
   

4. Final result is stored in dp[0][n-1];

So for higher lengths if starting and ending index is same then we recur for the remaining characters, since we have the sub-problem result stored so we computed that. In case start and end index character are different then we have added dp[start+1][end] and dp[start][end-1] that's similar to recur for leaving starting index and recur for leaving end index. But it would compute dp[start+1][end-1] twice and that why we have deducted that.

For proper understanding you can compute the table by hand for the string "aaaa" to understand how it's working.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int countPS(string s)
{

    int n = s.length();

    if (n == 0 || n == 1)
        return n;

    vector<vector<int> > dp(n);
    vector<vector<bool> > pal(n);

    for (int i = 0; i < n; i++) {
        dp[i] = vector<int>(n);
        pal[i] = vector<bool>(n);
    }

    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
        pal[i][i] = true;
        if (i == n - 1)
            break;
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = 3;
            pal[i][i + 1] = true;
        }
        else {
            dp[i][i + 1] = 2;
            pal[i][i + 1] = false;
        }
    }
    for (int len = 3; len <= n; len++) {
        for (int start = 0; start <= n - len; start++) {
            int end = start + len - 1;
            if (s[start] == s[end] && pal[start + 1][end - 1]) {
                dp[start][end] = dp[start + 1][end] + dp[start][end - 1] - dp[start + 1][end - 1] + 1;
                pal[start][end] = true;
            }
            else {
                dp[start][end] = dp[start + 1][end] + dp[start][end - 1] - dp[start + 1][end - 1];
                pal[start][end] = false;
            }
        }
    }
    return dp[0][n - 1];
}

int main()
{
    int t;

    cout << "Enter number of testcases\n";
    cin >> t;

    while (t--) {
        string str;

        cout << "Enter number of strings\n";
        cin >> str;

        cout << "Number of total palindromic substring is: " << countPS(str) << endl;
    }

    return 0;
}

Output:

Enter number of testcases
2
Enter number of strings
aaaa
Number of total palindromic substring is: 10
Enter number of strings
abaaba
Number of total palindromic substring is: 11