Palindromic Subsequences 只返回个数难度不大

//于任意字符串，如果头尾字符不相等，则字符串的回文子序列个数就等于去掉头的字符串的回文子序列个数+去掉尾的字
//符串的回文子序列个数-去掉头尾的字符串的回文子序列个数；如果头尾字符相等，那么除了上述的子序列个数之外，
//还要加上首尾相等时新增的子序列个数，1+去掉头尾的字符串的回文子序列个数，1指的是加上头尾组成的回文子序列，如aa，bb等。
//因此动态规划的状态转移方程为：
//设字符串为str，长度为n，p[i][j]表示第i到第j个字符间的最长子序列的长度（i<=j），则：
//状态初始条件：dp[i][i]=1 （i=0：n-1）
//状态转移方程：dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] if（str[i]！=str[j]）
// dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]+dp[i+1][j-1]+1=dp[i+1][j] + dp[i][j-1]+1 if （str[i]==str[j]）
public class PalindromicSubsequences {
int NumOfPalindromeSubSequence(String str){
int len=str.length();
int[][] dp=new int[str.length()-1][str.length()-1];

for(int i=0;i<len;i++){
dp[i][i]=1;
for(int j=i-1;j>=0;j--){
dp[j][i]=dp[j+1][i]+dp[j][i-1]-dp[j+1][i-1];
if(str.charAt(j)==str.charAt(i))
dp[j][i]+=1+dp[j+1][i-1];
}
}
return dp[0][len-1];
}
}