Задача: 730. Count Different Palindromic Subsequences
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей.

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

public class Solution {
    public int CountPalindromicSubsequences(string s) {
        const int MOD = 1000000007;
        int n = s.Length;
        int[,] dp = new int[n, n];

        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s[i] == s[j]) {
                    int l = i + 1, r = j - 1;
                    while (l <= r && s[l] != s[i]) l++;
                    while (l <= r && s[r] != s[j]) r--;
                    
                    if (l > r) {
                        dp[i, j] = dp[i + 1, j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i, j] = dp[i + 1, j - 1] * 2 + 1;
                    } else {
                        dp[i, j] = dp[i + 1, j - 1] * 2 - dp[l + 1, r - 1];
                    }
                } else {
                    dp[i, j] = dp[i + 1, j] + dp[i, j - 1] - dp[i + 1, j - 1];
                }

                dp[i, j] = (dp[i, j] + MOD) % MOD;
            }
        }

        return dp[0, n - 1];
    }
}

Ставь 👍 и забирай 📚 Базу знаний