Python | LeetCode

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 980. Unique Paths III Сложность: hard Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть: 1, представляющая начальную клетку. Существует ровно одна начальная клетка. 2, представляющая конечную клетку. Существует ровно одна конечная клетка. 0, представляющая пустые клетки, по которым можно ходить. -1, представляющая препятствия, по которым нельзя ходить. Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз. Пример:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

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

class Solution:
    def uniquePathsIII(self, grid: list[list[int]]) -> int:
        def backtrack(row, col, remain):
            if grid[row][col] == 2 and remain == 1:
                self.path_count += 1
                return

            temp = grid[row][col]
            grid[row][col] = -4
            remain -= 1

            for ro, co in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                next_row, next_col = row + ro, col + co

                if 0 <= next_row < self.rows and 0 <= next_col < self.cols and grid[next_row][next_col] >= 0:
                    backtrack(next_row, next_col, remain)

            grid[row][col] = temp

        non_obstacles = 0
        start_row = start_col = 0

        self.rows, self.cols = len(grid), len(grid[0])

        for row in range(self.rows):
            for col in range(self.cols):
                if grid[row][col] >= 0:
                    non_obstacles += 1
                if grid[row][col] == 1:
                    start_row, start_col = row, col

        self.path_count = 0
        backtrack(start_row, start_col, non_obstacles)

        return self.path_count

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

Задача: 485. Max Consecutive Ones Сложность: easy Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве. Пример:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

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

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        count = 0
        maxCount = 0
        for num in nums:
            if num == 1:
                count += 1
            else:
                maxCount = max(maxCount, count)
                count = 0
        return max(maxCount, count)

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 977. Squares of a Sorted Array Сложность: easy Дан целочисленный массив nums, отсортированный в неубывающем порядке. Верните массив квадратов каждого числа, отсортированный в неубывающем порядке. Пример:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

👨‍💻 Алгоритм: 1⃣Создайте массив квадратов каждого элемента. 2⃣Отсортируйте массив квадратов. 3⃣Верните отсортированный массив квадратов. 😎 Решение:

class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        ans = [num * num for num in nums]
        ans.sort()
        return ans

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

Концерт «ХЛЕБа», Финал Блиц Поинта и миллионы призовых! Tanks Blitz — в RuStore, ты — на Блиц Поинте в Москве (и на концерте «ХЛЕБа»). Скачай Tanks Blitz в RuStore, чтобы узнать больше о Финальном турнире Лиги Блиц Поинт, Часть 3 в Москве!⚡ Узнать больше #реклама 16+ apps.rustore.ru О рекламодателе

Задача: 565. Array Nesting Сложность: medium Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1]. Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила: Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k. Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее. Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат. Верните длину самого длинного множества s[k]. Пример:

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

👨‍💻 Алгоритм: 1⃣Создайте массив для отслеживания посещенных элементов. 2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент. 3⃣Обновите максимальную длину найденного множества. 😎 Решение:

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        visited = [False] * len(nums)
        max_length = 0
        
        for i in range(len(nums)):
            if not visited[i]:
                start = i
                count = 0
                while not visited[start]:
                    visited[start] = True
                    start = nums[start]
                    count += 1
                max_length = max(max_length, count)
        
        return max_length

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

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 435. Non-overlapping Intervals Сложность: medium Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались. Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

👨‍💻 Алгоритм: 1⃣Отсортируйте интервалы по времени окончания. 2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN. 3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans. 😎 Решение:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = 0
        k = float('-inf')
        
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                ans += 1
        
        return ans
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = 0
        k = float('-inf')
        
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                ans += 1
        
        return ans

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

Гайд по эффективным онлайн-встречам для отделов закупок Как специалистам по закупкам и тендерам экономить время на онлайн-совещаниях, сократить время на подготовку ТЗ и ускорить цикл закупок? Гайд МТС Линк — чек-листы, кейсы и подходы для упрощения коммуникации закупщиков с внутренними заказчиками и подрядчиками с помощью онлайн-встреч. ✅ В гайде: - Как создать постоянную ссылку на синки с коллегами или поставщиками и подключаться в 2 клика; - Как ускорить сбор требований без долгих переписок и конфликтов с юр.отделом; - Как обсуждать ТЗ и сразу фиксировать договоренности с помощью ИИ; - Как вести переговоры с подрядчиками и оперативно согласовать ключевые этапы сделки; - Как отслеживать выполнение условий контракта. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 826. Most Profit Assigning Work Сложность: medium У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где: difficulty[i] и profit[i] — сложность и прибыль i-го задания, worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]). Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз. Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0. Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям. Пример:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

👨‍💻 Алгоритм: 1⃣Создание и сортировка профиля работы Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности. 2⃣Обновление максимальной прибыли для каждой сложности Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли. 3⃣Вычисление максимальной прибыли Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее. 😎 Решение:

class Solution:
    def maxProfitAssignment(self, difficulty, profit, worker):
        jobProfile = [(0, 0)]
        for i in range(len(difficulty)):
            jobProfile.append((difficulty[i], profit[i]))
        jobProfile.sort()
        
        for i in range(1, len(jobProfile)):
            jobProfile[i] = (jobProfile[i][0], max(jobProfile[i][1], jobProfile[i-1][1]))
        
        netProfit = 0
        for ability in worker:
            l, r = 0, len(jobProfile) - 1
            jobProfit = 0
            while l <= r:
                mid = (l + r) // 2
                if jobProfile[mid][0] <= ability:
                    jobProfit = max(jobProfit, jobProfile[mid][1])
                    l = mid + 1
                else:
                    r = mid - 1
            netProfit += jobPro

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

Зарабатывайте на установках Яндекс Браузера Партнёрская программа для сервисных центров, магазинов компьютерной техники, сайтов для скачивания файлов и авторов статей. Вы можете предлагать его своим клиентам и аудитории — и зарабатывать на новых установках. Выплаты до 500₽ за каждую установку Яндекс Браузера. Подать заявку #реклама 0+ partner.browser.yandex.ru О рекламодателе

Задача: 253. Meeting Rooms II Сложность: medium Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов. Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

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

import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        heap = [intervals[0][1]]
        
        for i in range(1, len(intervals)):
            if intervals[i][0] >= heap[0]:
                heapq.heapreplace(heap, intervals[i][1])
            else:
                heapq.heappush(heap, intervals[i][1])
        
        return len(heap)

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

Задача: 1238. Circular Permutation in Binary Representation Сложность: medium Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Пример:

Input: arr = ["un","iq","ue"]
Output: 4

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

def maxLength(arr):
    def is_unique(s):
        return len(s) == len(set(s))

    def backtrack(index, current):
        if not is_unique(current):
            return 0
        max_length = len(current)
        for i in range(index, len(arr)):
            max_length = max(max_length, backtrack(i + 1, current + arr[i]))
        return max_length

    return backtrack(0, "")

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

Umnico Inbox: общайтесь с клиентами эффективнее Клиенты пишут в разные мессенджеры, а сотрудники путаются и не успевают оперативно отвечать? С Umnico Inbox вы сможете: 💻 Учитывать входящие сообщения клиентов из соцсетей, мессенджеров и сайтов объявлений в одном интерфейсе. 💰 Управлять воронкой продаж и повышать продажи на том же уровне трафика. Воронка легко настраивается под задачи и требования любого бизнеса. ✨ Автоматизировать ответы на частые вопросы и создать чат-бота на базе GPT-4 в удобном конструкторе. ✅ Работать с аудиторией в групповых чатах WhatsApp, Telegram и других мессенджеров, продвигая товары и услуги. ⚡ Настраивать уведомления на десктопе и мобильном, чтобы ни одно обращение от клиента не осталось без внимания. Попробуйте возможности Umnico Inbox бесплатно сегодня Узнать больше #реклама 16+ umnico.com О рекламодателе

Задача: 211. Design Add and Search Words Data Structure Сложность: medium Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову. Реализуйте класс WordDictionary: WordDictionary() инициализирует объект. void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже. bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой. Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

👨‍💻 Алгоритм: 1️⃣Инициализация и добавление слова: Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode. Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова. 2️⃣Поиск слова в узле: Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова. 3️⃣Поиск слова в структуре данных: Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false. 😎 Решение:

class WordDictionary:

    def __init__(self):
        self.trie = {}

    def addWord(self, word: str) -> None:
        node = self.trie
        for ch in word:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node["$"] = True

    def search(self, word: str) -> bool:

        def search_in_node(word, node) -> bool:
            for i, ch in enumerate(word):
                if ch not in node:
                    if ch == ".":
                        for x in node:
                            if x != "$" and search_in_node(word[i + 1:], node[x]):
                                return True
                    return False
                else:
                    node = node[ch]
            return "$" in node

        return search_in_node(word, self.trie)

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать

Задача: 518. Coin Change II Сложность: medium Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег. Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0. Предположим, что у вас есть бесконечное количество каждой монеты. Ответ гарантированно вписывается в знаковое 32-битное целое число. Пример:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

👨‍💻 Алгоритм: 1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты. 2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его. 3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу. 😎 Решение:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        def numberOfWays(i: int, amount: int) -> int:
            if amount == 0:
                return 1
            if i == len(coins):
                return 0
            if memo[i][amount] != -1:
                return memo[i][amount]

            if coins[i] > amount:
                memo[i][amount] = numberOfWays(i + 1, amount)
            else:
                memo[i][amount] = numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
            
            return memo[i][amount]

        memo = [[-1] * (amount + 1) for _ in range(len(coins))]
        return numberOfWays(0, amount)

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

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 656. Coin Path Сложность: hard Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y. Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

import heapq

def minCostPath(coins, maxJump):
    n = len(coins)
    if coins[0] == -1:
        return []
    
    dp = [float('inf')] * n
    dp[0] = coins[0]
    path = [[] for _ in range(n)]
    path[0] = [1]
    
    heap = [(coins[0], 0)]  # (cost, index)
    
    while heap:
        current_cost, i = heapq.heappop(heap)
        if current_cost > dp[i]:
            continue
        for k in range(1, maxJump + 1):
            if i + k < n and coins[i + k] != -1:
                new_cost = current_cost + coins[i + k]
                if new_cost < dp[i + k] or (new_cost == dp[i + k] and path[i] + [i + k + 1] < path[i + k]):
                    dp[i + k] = new_cost
                    path[i + k] = path[i] + [i + k + 1]
                    heapq.heappush(heap, (new_cost, i + k))
    
    return path[-1] if dp[-1] != float('inf') else []

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