字符串回文子序列的总个数问题

题目：输入一个字符串str，求其回文子序列的总个数。

说明：两个回文子序列，内容相同，但其构成字符在原字符串中的序列位置（下标）不同，它们是不同的回文子序列。

思路：
对于任意一个子序列，
如果首尾两字符不相同，则 该子序列的回文子序列个数 = 去掉首字符的字符串的回文子序列个数 + 去掉尾字符的字符串的回文子序列个数 – 去掉首尾字符的字符串的回文子序列个数。
如果首尾两字符 相同，在上式的基础上，还要加上当首尾字符相等时新增的回文子序列个数，即 去掉首尾字符的字符串的回文子序列个数 + 1，这里的 1 指的是 仅仅由首尾两个字符所构成的回文子序列。

该问题能够分解为一系列子问题，故使用动态规划算法来解决。

状态初始条件：

if (left == right)  //相同字符
    dp[left][right] = 1;  //回文子序列的数量为1

状态转移方程：

if (str[left] != str[right])
{
    dp[left][right] = dp[left][right-1] + dp[left+1][right] - dp[left+1][right-1];
}
else
{
    dp[left][right] = dp[left][right-1] + dp[left+1][right] - dp[left+1][right-1] + dp[left+1][right-1] + 1;
                    = dp[left][right-1] + dp[left+1][right] + 1;
}

由状态转移方程能够看出：
需要使用 dp[left+1][] 来推导 dp[left][] ，故left必须由 length-1 ——> 0，由大到小的递减顺序。
需要使用 dp[][right-1] 来推导 dp[][right] ，故right必须由 left + 1 ——> length-1，由小到大的递增顺序。

空间复杂度为 O(n^2)，时间复杂度为 O(n^2)。

使用Java语言实现：

    /**
    * @Description:动态规划求回文子序列的总个数
    * @Param:输入字符串str
    * @return:所输入字符串str的回文子序列的总个数
    * @Date: 2018/4/28
    **/
    static int SumofPalindrome(String str)
    {
        int length = str.length();
        int[][] count = new int[length][length];  //系统自动初始化为0

        for (int left = length - 1; left >= 0; left--)
        {
            count[left][left] = 1;

            for (int right = left + 1; right < length; right++)
            {
                if (str.charAt(left) == str.charAt(right))
                {
                    count[left][right] = count[left][right - 1] + count[left + 1][right] + 1;
                }
                else
                {
                    count[left][right] = count[left][right - 1] + count[left + 1][right] - count[left + 1][right - 1];
                }
            }
        }

        return count[0][length - 1];
    }