C/C++ | LeetCode

#medium Задача: 740. Delete and Earn Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз. Пример:

Input: nums = [3,4,2]
Output: 6

👨‍💻 Алгоритм: 1⃣Подсчитайте количество каждого числа в массиве nums. 2⃣Используйте динамическое программирование для расчета максимальных очков, которые можно заработать, используя накопленный результат для чисел, меньших текущего. Добавьте текущий день в стек. 3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки. 😎 Решение:

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        vector<int> uniqueNums;
        for (const auto& p : count) {
            uniqueNums.push_back(p.first);
        }
        sort(uniqueNums.begin(), uniqueNums.end());
        
        int avoid = 0, using = 0, prev = -1;
        for (int num : uniqueNums) {
            if (num - 1 != prev) {
                int newAvoid = max(avoid, using);
                using = num * count[num] + max(avoid, using);
                avoid = newAvoid;
            } else {
                int newAvoid = max(avoid, using);
                using = num * count[num] + avoid;
                avoid = newAvoid;
            }
            prev = num;
        }
        
        return max(avoid, using);
    }
};et(num) + Math.max(avoid, using);
                avoid = newAvoid;
            } else {
                int newAvoid = Math.max(avoid, using);
                using = num * count.get(num) + avoid;
                avoid = newAvoid;
            }
            prev = num;
        }
        
        return Math.max(avoid, using);
    }
}

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

Самое время создать и продвинуть свой сайт! 💻Веб-студия "ADM" - лаборатория, где разрабатываются методики, за счет которых путь к успеху будет быстрым, не дорогим, а главное - быстроокупаемым💰. Наши знания и 10 летний опыт работы помогут создать проект, приносящий прибыть с первого дня.⚡ ⚡Скидка по промокоду TELEGRAM 10% на все услуги!⚡ Услуги - разработка корпоративных сайтов, интернет-магазинов, информационных порталы, лендингов, - seo-продвижение, - контекстная реклама, - разработка логотипов, - веб-доработка, - хостинг, - настройки всех видов интернет рекламы, - бренд-буки, - разработка каталога, - разработка фирменного стиля. https://adm-lab.ru Узнать больше #реклама adm-lab.ru О рекламодателе

#medium Задача: 739. Daily Temperatures Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0. Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

👨‍💻 Алгоритм: 1⃣Создайте стек для хранения индексов дней с температурами, для которых еще не найден более теплый день. 2⃣Пройдите по массиву температур и для каждого дня: Пока текущая температура больше температуры дня на вершине стека, обновляйте массив ответов и удаляйте вершину стека. Добавьте текущий день в стек. 3⃣Возвращайте массив ответов. 😎 Решение:

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int> answer(n, 0);
        stack<int> stack;
        
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && T[i] > T[stack.top()]) {
                int j = stack.top();
                stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        
        return answer;
    }
};

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

#medium Задача: 738. Monotone Increasing Digits Целое число имеет монотонно возрастающие цифры тогда и только тогда, когда каждая пара соседних цифр x и y удовлетворяет x <= y. Задав целое число n, верните наибольшее число, которое меньше или равно n с монотонно возрастающими цифрами. Пример:

Input: n = 10
Output: 9

👨‍💻 Алгоритм: 1⃣Преобразуйте число в строку для удобства обработки. 2⃣Найдите позицию, где последовательность перестает быть монотонной. 3⃣Уменьшите соответствующую цифру и установите все последующие цифры в 9. 😎 Решение:

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string digits = to_string(N);
        int marker = digits.size();
        
        for (int i = digits.size() - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                marker = i;
                digits[i - 1]--;
            }
        }
        
        for (int i = marker; i < digits.size(); i++) {
            digits[i] = '9';
        }
        
        return stoi(digits);
    }
};

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

Узнайте, какая профессия в IT вам подходит. Бесплатно! Пройдите тест на профессию и забирайте: ✅ Бесплатную карьерную консультацию с экспертом ✅ Доступ к чат-боту с гайдами по профессиям и заданиями для самопроверки ✅ Мини-курсы для погружения в IT и дизайн, чтобы точнее выбрать направление ✨130 000 человек уже прошли профтестирование и выбрали перспективную профессию в IT или дизайне Пройдите тест за 5 минут! Начать #реклама 16+ free.skillfactory.ru О рекламодателе

#medium Задача: 737. Sentence Similarity II Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

👨‍💻 Алгоритм: 1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false. 2⃣Построить граф схожести слов с использованием словаря. 3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях. 😎 Решение:

class Solution {
public:
    bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        if (sentence1.size() != sentence2.size()) {
            return false;
        }

        unordered_map<string, vector<string>> graph;
        for (const auto& pair : similarPairs) {
            graph[pair[0]].push_back(pair[1]);
            graph[pair[1]].push_back(pair[0]);
        }

        for (size_t i = 0; i < sentence1.size(); ++i) {
            if (sentence1[i] != sentence2[i] && !dfs(sentence1[i], sentence2[i], graph, unordered_set<string>())) {
                return false;
            }
        }

        return true;
    }

private:
    bool dfs(const string& word1, const string& word2, unordered_map<string, vector<string>>& graph, unordered_set<string> visited) {
        if (word1 == word2) {
            return true;
        }
        visited.insert(word1);
        for (const string& neighbor : graph[word1]) {
            if (visited.find(neighbor) == visited.end() && dfs(neighbor, word2, graph, visited)) {
                return true;
            }
        }
        return false;
    }
};

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

Ты готов к ИТ-собеседованию? Бесплатный воркшоп 20 марта Приглашаем айтишников на воркшоп "Искусство продавать себя или как подготовиться к собесу на все 100" Рекрутер раскроет все карты! Записывайся на воркшоп, чтобы первым узнать: — Как подготовиться к собеседованию — Как презентовать свой опыт так, чтобы тебя запомнили — Как проверяют hard skills и как к этому подготовиться — Как произвести хорошее впечатление, запомниться рекрутеру и сделать так, чтобы захотели работать именно с тобой Дата: 20 марта, 18:00 Где: Онлайн Регистрируйся, чтобы получить полезные знания и быть готовым к следующему собеседованию на 100% Зарегистрироваться #реклама 16+ my.mts-link.ru О рекламодателе

#hard Задача: 736. Parse Lisp Expression Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся. Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

👨‍💻 Алгоритм: 1⃣Определите функцию для оценки выражений. 2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных). 3⃣Используйте словарь для отслеживания значений переменных с учетом области видимости. 😎 Решение:

class Solution {
public:
    int evaluate(string expression) {
        return evaluate(expression, {});
    }

private:
    int evaluate(string expression, unordered_map<string, int> env) {
        if (expression[0] != '(') {
            if (isdigit(expression[0]) || expression[0] == '-') {
                return stoi(expression);
            }
            return env[expression];
        }

        vector<string> tokens = tokenize(expression);
        if (tokens[0] == "let") {
            for (size_t i = 1; i < tokens.size() - 2; i += 2) {
                env[tokens[i]] = evaluate(tokens[i + 1], env);
            }
            return evaluate(tokens.back(), env);
        } else if (tokens[0] == "add") {
            return evaluate(tokens[1], env) + evaluate(tokens[2], env);
        } else if (tokens[0] == "mult") {
            return evaluate(tokens[1], env) * evaluate(tokens[2], env);
        }
        return 0;
    }

    vector<string> tokenize(const string& expression) {
        vector<string> tokens;
        string token;
        int parens = 0;
        istringstream iss(expression);
        char c;

        while (iss >> c) {
            if (c == '(') {
                parens++;
                if (parens == 1) continue;
            } else if (c == ')') {
                parens--;
                if (parens == 0) {
                    tokens.push_back(tokenize(token));
                    token = "";
                    continue;
                }
            } else if (c == ' ' && parens == 1) {
                if (!token.empty()) {
                    tokens.push_back(token);
                    token = "";
                }
                continue;
            }
            token += c;
        }
        if (!token.empty()) {
            tokens.push_back(token);
        }
        return tokens;
    }
};

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

VisGPT — твой личный суперпомощник! 👌😊 20+ нейросетей для любых задач: Написание текстов Создание картинок Анализ данных Помощь с кодом Генерация идей 👍 Преимущества VisGPT Всё в одном приложении Без VPN и сложных настроек Удобная оплата в рублях Доступные тарифы Поддержка 24/7 💰 Специальное предложение: Годовая подписка со скидкой 20% Начни использовать прямо сейчас: Начать #реклама 16+ ai.vis.center О рекламодателе

#medium Задача: 735. Asteroid Collision Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

👨‍💻 Алгоритм: 1⃣Используйте стек для отслеживания движущихся вправо астероидов. 2⃣Пройдите по массиву астероидов: Если астероид движется вправо, добавьте его в стек. Если астероид движется влево, сравните его с последним астероидом в стеке (если он есть и движется вправо): Если движущийся вправо астероид больше, текущий взорвется. Если движущийся влево астероид больше, последний астероид в стеке взорвется, и продолжите сравнение. Если они одинакового размера, оба взорвутся. 3⃣Добавьте оставшиеся астероиды из стека и текущий астероид в результат. 😎 Решение:

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> stack;
        
        for (int asteroid : asteroids) {
            bool alive = true;
            while (alive && asteroid < 0 && !stack.empty() && stack.back() > 0) {
                int last = stack.back();
                stack.pop_back();
                if (last == -asteroid) {
                    alive = false;
                } else if (last > -asteroid) {
                    stack.push_back(last);
                    alive = false;
                }
            }
            if (alive) {
                stack.push_back(asteroid);
            }
        }
        
        return stack;
    }
};

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

Бесплатный курс по дизайну в FIGMA Онлайн-программа с наставником и чатом. Осторожно! 80% практики. По результату обучения у вас будет портфолио из нескольких работ. Сертификат о прохождении курса. Возможность пройти полное обучение и получить гарантированное трудоустройство! Учитесь дизайну у профессионалов. Переходи по кнопки: "Узнать больше" и начинай свое обучение. Доступ 0 руб. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

#easy Задача: 734. Sentence Similarity Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

👨‍💻 Алгоритм: 1⃣Проверьте, равны ли длины предложений sentence1 и sentence2. Если нет, верните false. 2⃣Создайте словарь для хранения всех пар похожих слов. 3⃣Проверьте каждую пару слов из предложений sentence1 и sentence2 на схожесть, используя словарь и правило, что слово всегда похоже на само себя. 😎 Решение:

class Solution {
public:
    bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        if (sentence1.size() != sentence2.size()) {
            return false;
        }

        unordered_map<string, unordered_set<string>> similar;
        for (const auto& pair : similarPairs) {
            similar[pair[0]].insert(pair[1]);
            similar[pair[1]].insert(pair[0]);
        }

        for (int i = 0; i < sentence1.size(); ++i) {
            const string& w1 = sentence1[i];
            const string& w2 = sentence2[i];
            if (w1 != w2 && (similar[w1].find(w2) == similar[w1].end())) {
                return false;
            }
        }

        return true;
    }
};

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

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Открытые школы Т1 — карьерная программа для начинающих ИТ-специалистов от ИТ-холдинга Т1. Это ИТ-интенсив без отрыва от работы и карьерный трек в Т1 для лучших выпусников. Что тебя ждет? ✅ Бесплатный онлайн-интенсив с топовыми преподавателями ✅ Практические задачи и индивидуальная обратная связь ✅ Поддержка HR и знакомство с ИТ-командами Т1 ✅ Карьерный фаст-трек: навыки для роста из джуна в мидла ✅ Реальный шанс получить оффер в ИТ-холдинг Т1 Более 1000 специалистов уже прошли этот путь — теперь твоя очередь! Подавай заявку до 14 марта и приходи учиться! Старт ИТ-интенсива уже 17 марта. Подать заявку #реклама 16+ t1.ru О рекламодателе

#easy Задача: 733. Flood Fill Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки. Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

👨‍💻 Алгоритм: 1⃣Получите цвет начального пикселя. 2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет. 3⃣Обновите изображение и верните его. 😎 Решение:

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) {
            return image;
        }
        
        dfs(image, sr, sc, originalColor, color);
        return image;
    }
    
private:
    void dfs(vector<vector<int>>& image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != originalColor) {
            return;
        }
        image[x][y] = newColor;
        dfs(image, x + 1, y, originalColor, newColor);
        dfs(image, x - 1, y, originalColor, newColor);
        dfs(image, x, y + 1, originalColor, newColor);
        dfs(image, x, y - 1, originalColor, newColor);
    }
};

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

Чек-лист для ревизии ИТ-инфраструктуры Для собственников бизнеса и ИТ-специалистов. 👌 Самостоятельно проверьте ИТ инфраструктуру компании: ✅ Доступность и надёжность ✅ Масштабирование и развитие ✅ Информационная безопасность Узнать больше #реклама cloud.rosukrep.ru О рекламодателе

#hard Задача: 732. My Calendar III k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование. Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

👨‍💻 Алгоритм: 1⃣Создайте два словаря для хранения изменений времени бронирования: один для начала событий, другой для конца событий. 2⃣Для каждого нового события обновите словари начала и конца событий. 3⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий. 😎 Решение:

class MyCalendarThree {
public:
    MyCalendarThree() {}

    int book(int startTime, int endTime) {
        events[startTime]++;
        events[endTime]--;
        
        int active = 0;
        int maxActive = 0;
        for (const auto& [time, count] : events) {
            active += count;
            maxActive = max(maxActive, active);
        }
        
        return maxActive;
    }

private:
    map<int, int> events;
};

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

#medium Задача: 731. My Calendar II Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь. Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

👨‍💻 Алгоритм: 1⃣Создайте два списка: один для отслеживания всех событий, второй для отслеживания пересечений. подпоследовательностей. 2⃣При добавлении нового события сначала проверьте, не пересекается ли оно с любыми существующими пересечениями. 3⃣Если пересечение не обнаружено, добавьте новое событие и обновите список пересечений при необходимости. 😎 Решение:

class MyCalendarTwo {
public:
    MyCalendarTwo() {}

    bool book(int start, int end) {
        for (const auto& overlap : overlaps) {
            if (start < overlap[1] && end > overlap[0]) {
                return false;
            }
        }
        for (const auto& event : events) {
            if (start < event[1] && end > event[0]) {
                overlaps.push_back({max(start, event[0]), min(end, event[1])});
            }
        }
        events.push_back({start, end});
        return true;
    }

private:
    vector<pair<int, int>> events;
    vector<pair<int, int>> overlaps;
};

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

Системный администратор Linux с нуля Бесплатный курс от Selectel Старт — 1 марта Освойте администрирование Linux на SelectOS. После курса вы сможете: - управлять инфраструктурой на базе Linux; - работать с командной строкой и основными утилитами; - управлять пользователями, файлами и правами доступа; - настраивать сети, SSH-соединения и мониторинг системы; - управлять пакетами и обновлениями программного обеспечения; - анализировать логи и устранять инциденты. Смотреть #реклама 16+ promo.selectel.ru О рекламодателе

#hard Задача: 730. Count Different Palindromic Subsequences Поскольку ответ может быть очень большим, верните его по модулю 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 на основе состояния предыдущих подстрок. 😎 Решение:

class Solution {
public:
    int countPalindromicSubsequences(string s) {
        const int MOD = 1000000007;
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        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];
    }
};

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