Задача: 516. Longest Palindromic Subsequence
Сложность: medium

Дана строка s, найдите длину самой длинной палиндромной подпоследовательности в s.
Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов.

Пример:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

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

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте двумерный массив memo размером n на n, где memo[i][j] содержит длину самой длинной палиндромной подпоследовательности подстроки, сформированной от индекса i до j в s.

2⃣Верните lps(s, 0, n - 1, memo), где lps — это рекурсивный метод с четырьмя параметрами: s, начальный индекс подстроки как i, конечный индекс подстроки как j и memo. Если memo[i][j] != 0, это означает, что мы уже решили эту подзадачу, поэтому возвращаем memo[i][j]. Если i > j, строка пуста, возвращаем 0. Если i == j, это подстрока, содержащая один символ, возвращаем 1.

3⃣Если первый и последний символы совпадают, т.е. s[i] == s[j], включаем эти два символа в палиндромную подпоследовательность и добавляем её к самой длинной палиндромной подпоследовательности, сформированной с использованием подстроки от индекса i + 1 до j - 1. Выполняем memo[i][j] = lps(s, i + 1, j - 1, memo) + 2. Если первый и последний символы не совпадают, рекурсивно ищем самую длинную палиндромную подпоследовательность в обеих подстроках, сформированных после игнорирования первого и последнего символов. Выбираем максимум из этих двух и выполняем memo[i][j] = max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo)). Возвращаем memo[i][j].

😎 Решение:

class Solution {
    function longestPalindromeSubseq($s) {
        $n = strlen($s);
        $memo = [];
        
        function lps($s, $l, $r, &$memo) {
            $key = $l . "," . $r;
            if (isset($memo[$key])) return $memo[$key];
            if ($l > $r) return 0;
            if ($l == $r) return 1;
            
            if ($s[$l] == $s[$r]) {
                $memo[$key] = lps($s, $l + 1, $r - 1, $memo) + 2;
            } else {
                $memo[$key] = max(lps($s, $l, $r - 1, $memo), lps($s, $l + 1, $r, $memo));
            }
            return $memo[$key];
        }
        
        return lps($s, 0, $n - 1, $memo);
    }
}

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