thanks a lot.What would be its time complexity O(n*k)?

This is the correct relation imo.

Let me explain it further.

dp[i][j][k] means the number of palindromic subsequences of size k that occur between i and j (inclusive)

So if s[i]==s[j], this would mean that the corner elements are same at the ith and the jth index, so we multiply it with dp[i+1][j-1][k-2] (this means that we exclude ith and jth index and find the number of palindromic subsequences of size k-2 from i+1 to j-1 indices).

Again we add dp[i][j-1][k] and dp[i+1][j][k] and subtract dp[i+1][j-1][k] from it which is self explanatory.

Number of palindromic subsequences of size 1 between i & j will be j-i+1 ( as all strings of size 1 are palindrome) Number of palindromic subsequences of size 0 between i & j will be 1 Number of palindromic subsequences of size 2 when i+1==j and ith and jth character are equal will be 1 else it will be 0

int PalindromicSubsequencesOfSizeK(string s, int KK){
    vector<vector<vector<int>>>dp(n+2, vector<vector<int>>(n+2, vector<int>(KK+1,0)));
    for(int i=n;i>=1;i--){
        for(int j=i;j<=n;j++){
            dp[i][j][0]=1;
            dp[i][j][1]=j-i+1;
            if(i+1==j){
                if(s[i-1]==s[j-1])dp[i][j][2]=1;
                continue;
            }
            for(int k=3;k<=KK;k++){
                dp[i][j][k]=(s[i-1]==s[j-1])*dp[i+1][j-1][k-2]+dp[i][j-1][k]+dp[i+1][j][k]-dp[i+1][j-1][k];
            }
        }
    }
    return dp[1][n][KK];
}