leetcode：730. Statistics of different palindrome subsequences [traversed by point and surface interval DP + 3D DP + diagonal]

analysis

use dp[x][i][j] It means that the beginning and the end are x Of s[i:j]( Contains two endpoints ） The number of different palindrome strings
Four situations ：
1. if s[i] = s[j] = x: dp[x][i][j] = (2 + sum(d[i + 1][j - 1] for d in dp)) % MOD Add two yes x and xx
Get rid of any other characters that can start and end in the middle So it is sum
2. If only s[i] = x:dp[x][i][j] = dp[k][i][j - 1] Lose the last
3. If only s[j] = x:dp[x][i][j] = dp[k][i + 1][j] Lose the first
4. If not x：dp[k][i][j] = dp[k][i + 1][j - 1] Throw it all away

Then initially we can get each dp[x][i][i] All are 1 It looks like , Is a main diagonal
Because we are going to d[i + 1][j - 1] So it's equivalent to considering the next grid and the left grid
therefore , We need to traverse diagonally

Finally back to sum(d[0][n - 1] for d in dp) % MOD

ac code

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        # dp[c][i][j]  It means that s[i:j] With c Number of different palindrome strings at the beginning and end 
        #  From point to face 
        MOD = 10 ** 9 + 7
        n = len(s)

        # abcd
        dp = [[[0] * n for _ in range(n)] for _ in range(4)]

        # dp[c][i][i] = 1
        for i, c in enumerate(s):
            dp[ord(c) - ord('a')][i][i] = 1

        for diff in range(1, n):
            for j in range(diff, n):
                i = j - diff
                for k, c in enumerate("abcd"):
                    # xx and x => 2
                    if s[i] == c and s[j] == c:
                        dp[k][i][j] = (2 + sum(d[i + 1][j - 1] for d in dp)) % MOD                  
                    # drop s[j]
                    elif s[i] == c:
                        dp[k][i][j] = dp[k][i][j - 1]
                    # drop s[i]
                    elif s[j] == c:
                        dp[k][i][j] = dp[k][i + 1][j]
                    # drop s[i] + s[j]
                    else:
                        dp[k][i][j] = dp[k][i + 1][j - 1]
        return sum(d[0][n - 1] for d in dp) % MOD

summary

Consider from point to surface
Spread one by one i and j Move out
So it's a diagonal calculation
Then the initial conditions are simple
There are four other shifts that can be understood
So the palindrome string can be considered by the interval of point and surface dp 了
The special thing here is to separate each letter as a dimension