Задача: 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 на основе состояния предыдущих подстрок.

😎 Решение:

function countPalindromicSubsequences($s) {
    $MOD = 1000000007;
    $n = strlen($s);
    $dp = array_fill(0, $n, array_fill(0, $n, 0));

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

    for ($length = 2; $length <= $n; $length++) {
        for ($i = 0; $i <= $n - $length; $i++) {
            $j = $i + $length - 1;
            if ($s[$i] == $s[$j]) {
                $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];
}

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