子序列——回文子序列个数（七）

LeetCode_730_CountDifferentPalindromicSubsequences

题目分析：

这是一个状态稍微复杂的题。dp的递推过程也是比较少见，我是第一次见。不过看懂后其实不难。
首先，我们不再是单纯地从左往右或者从右往左推，而是从两边往中间，
为什么呢，递归方式当然是跟随题目变化，也没人说不能酱紫呀。
定义dp[i][j]为字符串 i开头 j结尾 的子串的回文子序列个数。
观察左右两端的字符
1.不相等。S.charAt(i) != S.charAt(j)
  dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
  就是等于 右边少一个 加上左边少一个 的情况，最后减去左右各少一个的情况，去重。
2.相等。S.charAt(i) == S.charAt(j)
  稍微复杂一点了，根据ij中间是否有和S.charAt(i)相同的字符，要分三种情况
  2.1没有两边相同的字字符
    dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
    假设为b 无重复 那么等于中间个数 * 2 + 2
    乘2是因为中间任意回文子序列都可以和首位加上b组成新的
    +2是因为内部没有b 所以b和bb都是新的
  2.2有且只有一个相同的字符
    dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
    假设为b 重复1个 那么等于中间个数 * 2 + 1
    乘2是因为中间任意回文子序列都可以和首位加上b组成新的
    +1是因为内部有b 只有bb是新的
  2.3有且有两个以上相同字符
    dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
    假设为b 重复2个以上 那么等于中间个数 * 2 - 内部bb的首位组成的串的个数
    乘2是因为中间任意回文子序列都可以和首位加上b组成新的
    -内部bb的首位组成的串的个数 去重 (b和bb都被内部bb的首位组成的串算上了 也就不用+1 +2)
递推初始项
  for (int i = 0; i < n; ++i) dp[i][i] = 1;
  1.为何是对角线，注意ij的定义，ij只差越大，代表串越长，
    我们的串，随着递推过程逐渐变短直到为1，这里对角线是最短字符串，
    相当于递归的边界条件。
  2.为何是1，也就是对角线，对角线开始和结束一样，也就是1个字符，当然是1.
    b c c b
  b 1 2 3 6
  c 0 1 2 3
  c 0 0 1 2
  b 0 0 0 1
递推过程
  从对角线，"逐斜行"往右上推，第一次见。

解法：

public static int countPalindromicSubsequences(String S) {
    int n = S.length(), M = 1000000007;
    int [][]dp = new int[n][n];
    for (int i = 0; i < n; ++i) dp[i][i] = 1;
    for (int len = 1; len < n; ++len) {
        for (int i = 0; i < n - len; ++i) {
            int j = i + len;
            if (S.charAt(i) == S.charAt(j)) {
                /**
                 * 这三句本质是为了求中间有多少个和左右两边相等的个数
                 * 使用双指针往中间移动到第一个等于两边数的情况
                 * left > right 表示没有重复 这种情况left能走到最右 right能走到最左
                 * left == right 表示只有一个重复 left right都在中间停下了
                 * left < right 表示至少2个重复
                 */
                int left = i + 1, right = j - 1;
                while (left <= right && S.charAt(left) != S.charAt(i)) ++left;
                while (left <= right && S.charAt(right) != S.charAt(i)) --right;

                if (left > right) {
                    /**
                     * 假设为b 无重复 那么等于中间个数 * 2 + 2
                     * 乘2是因为中间任意回文子序列都可以和首位加上b组成新的
                     * +2是因为内部没有b 所以b和bb都是新的
                     */
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                } else if (left == right) {
                    /**
                     * 假设为b 重复1个 那么等于中间个数 * 2 + 1
                     * 乘2是因为中间任意回文子序列都可以和首位加上b组成新的
                     * +1是因为内部有b 只有bb是新的
                     */
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                } else {
                    /**
                     * 假设为b 重复2个以上 那么等于中间个数 * 2 - 内部bb的首位组成的串的个数
                     * 乘2是因为中间任意回文子序列都可以和首位加上b组成新的
                     * -内部bb的首位组成的串的个数 去重 (b和bb都被内部bb的首位组成的串算上了 也就不用+1 +2)
                     */
                    dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
                }
            } else {
                /**
                 * 不相等 那么等于
                 * 右边少一个
                 * 加上左边少一个
                 * "减去"左右各少一个(最后这个减去 也是去重操作)
                 */
                dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
            }
            /**
             * 这是个漂亮的取模操作 将有的情况直接用+代替了%
             */
            dp[i][j] = (dp[i][j] < 0) ? dp[i][j] + M : dp[i][j] % M;
        }
    }
    return dp[0][n - 1];
}