Задача: 727. Minimum Window Subsequence
Сложность: hard

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

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

2⃣Поддерживайте счетчики для символов в текущем окне и требуемых символов из s2.

3⃣Перемещайте правый указатель, чтобы найти подходящее окно, и левый указатель, чтобы минимизировать его.

😎 Решение:

func minWindow(_ s1: String, _ s2: String) -> String {
    if s1.isEmpty || s2.isEmpty {
        return ""
    }

    var dictT = [Character: Int]()
    for char in s2 {
        dictT[char, default: 0] += 1
    }

    let required = dictT.count
    var l = 0, r = 0, formed = 0
    var windowCounts = [Character: Int]()
    var ans = (length: Int.max, start: 0, end: 0)
    let s1Array = Array(s1)

    while r < s1Array.count {
        let char = s1Array[r]
        windowCounts[char, default: 0] += 1

        if let count = dictT[char], windowCounts[char] == count {
            formed += 1
        }

        while l <= r && formed == required {
            let char = s1Array[l]

            if r - l + 1 < ans.length {
                ans = (r - l + 1, l, r)
            }

            windowCounts[char, default: 0] -= 1
            if let count = dictT[char], windowCounts[char]! < count {
                formed -= 1
            }

            l += 1
        }

        r += 1
    }

    return ans.length == Int.max ? "" : String(s1Array[ans.start...ans.end])
}

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

Задача: №19. Remove Nth Node From End of List
Сложность: medium

Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.

Пример:

Input: head = [1,2,3,4,5], n = 2  
Output: [1,2,3,5]  

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

1⃣Создать фиктивный узел, который указывает на head, чтобы упростить удаление первого элемента.

2⃣Использовать два указателя: один сместить на n шагов вперед, затем двигать оба, пока первый не достигнет конца.

3⃣Удалить нужный узел, изменив ссылки, и вернуть новый head.

😎 Решение:

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy = ListNode(0)
        dummy.next = head
        
        var prev: ListNode? = dummy
        var post: ListNode? = dummy
        
        for _ in 0..<n {
            post = post?.next
        }
        
        while post?.next != nil {
            prev = prev?.next
            post = post?.next
        }
        
        prev!.next = prev!.next!.next
        
        return dummy.next
    }
}

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

Задача: 159. Longest Substring with At Most Two Distinct Characters
Сложность: medium

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

Пример:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

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

1⃣Возвратить N, если длина строки N меньше 3. Установить оба указателя в начало строки left = 0 и right = 0 и инициализировать максимальную длину подстроки max_len = 2.

2⃣Пока указатель right меньше N:
Если в хэшмапе меньше 3 различных символов, добавить текущий символ s[right] в хэшмап и переместить указатель right вправо.
Если в хэшмапе 3 различных символа, удалить самый левый символ из хэшмапа и переместить указатель left, чтобы скользящее окно содержало только 2 различных символа.

3⃣Обновить max_len.

😎 Решение:

func lengthOfLongestSubstringTwoDistinct(_ s: String) -> Int {
    let n = s.count
    if n < 3 { return n }

    var left = 0
    var right = 0
    var hashmap: [Character: Int] = [:]

    var maxLen = 2

    let sArray = Array(s)
    while right < n {
        hashmap[sArray[right]] = right
        right += 1

        if hashmap.count == 3 {
            let delIdx = hashmap.values.min()!
            hashmap.removeValue(forKey: sArray[delIdx])
            left = delIdx + 1
        }

        maxLen = max(maxLen, right - left)
    }
    return maxLen
}

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

Задача: 410. Split Array Largest Sum
Сложность: easy

Учитывая целочисленный массив nums и целое число k, разбейте nums на k непустых подмассивов так, чтобы наибольшая сумма любого подмассива была минимальна. Верните минимизированную наибольшую сумму разбиения. Подмассив - это смежная часть массива.

Пример:

Input: nums = [7,2,5,10,8], k = 2
Output: 18

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

1⃣Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.

2⃣Выполните бинарный поиск по этим границам. Для каждой средней суммы проверьте, можно ли разбить массив на k подмассивов, чтобы максимальная сумма подмассива не превышала эту среднюю сумму.

3⃣Если возможно разбить массив для данной средней суммы, уменьшите верхнюю границу. Если нет, увеличьте нижнюю границу. Повторяйте до тех пор, пока границы не сойдутся.

😎 Решение:

func splitArray(_ nums: [Int], _ k: Int) -> Int {
    var left = nums.max()!
    var right = nums.reduce(0, +)
    while left < right {
        let mid = (left + right) / 2
        if canSplit(nums, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canSplit(_ nums: [Int], _ k: Int, _ maxSum: Int) -> Bool {
    var currentSum = 0
    var subarrays = 1
    for num in nums {
        if currentSum + num > maxSum {
            currentSum = num
            subarrays += 1
            if subarrays > k {
                return false
            }
        } else {
            currentSum += num
        }
    }
    return true
}

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

Задача: №45. Jump Game II
Сложность: medium

Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums[0].
Каждый элемент nums[i] представляет максимальную длину прямого перехода от индекса i.
Возвращает минимальное количество переходов для достижения nums[n - 1].

Пример:

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

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

1⃣Использовать greedy-подход: отслеживать текущий диапазон прыжков.

2⃣Обновлять дальность прыжка и увеличивать счетчик прыжков при выходе за пределы текущего диапазона.

3⃣Остановиться, как только достигнем последнего индекса.

😎 Решение:

class Solution {
    func jump(_ nums: [Int]) -> Int {
        var jumps = 0, farthest = 0, end = 0
        
        for i in 0..<nums.count - 1 {
            farthest = max(farthest, i + nums[i])
            
            if i == end {
                jumps += 1
                end = farthest
            }
        }
        
        return jumps
    }
}

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

Задача: 125. Valid Palindrome
Сложность: easy

Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.

Для данной строки s верните true, если она является палиндромом, и false в противном случае.

Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

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

1⃣Поскольку входная строка содержит символы, которые нам нужно игнорировать при проверке на палиндром, становится трудно определить реальную середину нашего палиндромического ввода.

2⃣Вместо того, чтобы двигаться от середины наружу, мы можем двигаться внутрь к середине! Если начать перемещаться внутрь, с обоих концов входной строки, мы можем ожидать увидеть те же символы в том же порядке.

3⃣Результирующий алгоритм прост:
1. Установите два указателя, один на каждом конце входной строки.
2. Если ввод является палиндромом, оба указателя должны указывать на эквивалентные символы в любой момент времени.
3. Если это условие не выполняется в какой-либо момент времени, мы прерываемся и возвращаемся раньше.
4. Мы можем просто игнорировать неалфавитно-цифровые символы, продолжая двигаться дальше.
5. Продолжайте перемещение внутрь, пока указатели не встретятся в середине.

😎 Решение:

class Solution {
    func isPalindrome(_ s: String) -> Bool {
        let characters = Array(s.lowercased())
        var i = 0
        var j = characters.count - 1

        while i < j {
            while i < j && !characters[i].isLetter && !characters[i].isNumber {
                i += 1
            }
            while i < j && !characters[j].isLetter && !characters[j].isNumber {
                j -= 1
            }

            if characters[i] != characters[j] {
                return false
            }

            i += 1
            j -= 1
        }

        return true
    }
}

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

Задача: 124. Binary Tree Maximum Path Sum
Сложность: hard

Вам дан массив цен, где prices[i] — это цена данной акции в i-й день.

Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить не более двух транзакций.

Пример:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1

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

1⃣Наивная реализация этой идеи заключалась бы в разделении последовательностей на две части и последующем перечислении каждой из подпоследовательностей, хотя это определенно не самое оптимизированное решение.
Для последовательности длиной N у нас было бы N возможных разделений (включая отсутствие разделения), каждый элемент был бы посещен один раз в каждом разделении. В результате общая временная сложность этой наивной реализации составила бы O(N²).

2⃣Мы могли бы сделать лучше, чем наивная реализация O(N²). Что касается алгоритмов разделяй и властвуй,
одна из общих техник, которую мы можем применить для оптимизации временной сложности, называется динамическим программированием (DP), где мы меняем менее повторяющиеся вычисления на некоторое дополнительное пространство.
В алгоритмах динамического программирования обычно мы создаем массив одного или двух измерений для сохранения промежуточных оптимальных результатов. В данной задаче мы бы использовали два массива, один массив сохранял бы результаты последовательности слева направо, а другой массив сохранял бы результаты последовательности справа налево. Для удобства мы могли бы назвать это двунаправленным динамическим программированием.

3⃣Сначала мы обозначаем последовательность цен как Prices[i], с индексом начиная от 0 до N-1. Затем мы определяем два массива, а именно left_profits[i] и right_profits[i].
Как следует из названия, каждый элемент в массиве left_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в левой подпоследовательности цен от индекса ноль до i, (т.е. Prices[0], Prices[1], ... Prices[i]).
Например, для подпоследовательности [7, 1, 5] соответствующий left_profits[2] будет равен 4, что означает покупку по цене 1 и продажу по цене 5.
И каждый элемент в массиве right_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в правой подпоследовательности цен от индекса i до N-1, (т.е. Prices[i], Prices[i+1], ... Prices[N-1]).
Например, для правой подпоследовательности [3, 6, 4] соответствующий right_profits[3] будет равен 3, что означает покупку по цене 3 и продажу по цене 6.
Теперь, если мы разделим последовательность цен вокруг элемента с индексом i на две подпоследовательности, с левыми подпоследовательностями как Prices[0], Prices[1], ... Prices[i] и правой подпоследовательностью как Prices[i+1], ... Prices[N-1],
то общая максимальная прибыль, которую мы получим от этого разделения (обозначенная как max_profits[i]), может быть выражена следующим образом:
max_profits[i] = left_profits[i] + right_profits[i+1]

😎 Решение:

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.count <= 1 {
            return 0
        }

        let length = prices.count
        var leftMin = prices[0]
        var rightMax = prices.last!

        var leftProfits = Array(repeating: 0, count: length)
        var rightProfits = Array(repeating: 0, count: length + 1)

        for l in 1..<length {
            leftProfits[l] = max(leftProfits[l - 1], prices[l] - leftMin)
            leftMin = min(leftMin, prices[l])

            let r = length - 1 - l
            rightProfits[r] = max(rightProfits[r + 1], rightMax - prices[r])
            rightMax = max(rightMax, prices[r])
        }

        var maxProfit = 0
        for i in 0..<length {
            maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i + 1])
        }

        return maxProfit
    }
}

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

Задача: 461. Hamming Distance
Сложность: easy

Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.

Даны два целых числа x и y, верните расстояние Хэмминга между ними.

Пример:

Input: x = 3, y = 1
Output: 1

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

1⃣Во-первых, стоит упомянуть, что в большинстве (или, по крайней мере, во многих) языков программирования есть встроенные функции для подсчета битов, установленных в 1. Если вам нужно решить такую задачу в реальном проекте, то лучше использовать эти функции, чем изобретать велосипед.

2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов.

3⃣Пошаговый подсчет битов:
Выполните побитовое XOR между x и y.
Инициализируйте счетчик bitCount = 0.
Пока число не равно нулю:
Если текущий бит равен 1, увеличьте bitCount.
Сдвиньте число вправо на один бит.
Возвращайте bitCount.

😎 Решение:

class Solution {
    func hammingDistance(_ x: Int, _ y: Int) -> Int {
        return (x ^ y).nonzeroBitCount
    }
}

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

Задача: 232. Implement Queue using Stacks
Сложность: easy

Реализуйте очередь (FIFO) с использованием только двух стеков. Реализованная очередь должна поддерживать все функции обычной очереди (push, peek, pop и empty).

Реализуйте класс MyQueue:

void push(int x) добавляет элемент x в конец очереди.
int pop() удаляет элемент из начала очереди и возвращает его.
int peek() возвращает элемент из начала очереди.
boolean empty() возвращает true, если очередь пуста, и false в противном случае.

Пример:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

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

1⃣Добавление элемента: Для метода push(int x) переместите все элементы из стека s1 в стек s2. Добавьте элемент x в стек s2. Затем переместите все элементы обратно из стека s2 в стек s1. Если стек s1 пуст, обновите переменную front значением x.

2⃣Удаление и проверка первого элемента: Для метода pop() удалите элемент из начала очереди, извлекая верхний элемент из стека s1. Обновите переменную front на новый верхний элемент стека s1, если он не пуст. Для метода peek() верните значение переменной front, так как она всегда хранит первый элемент очереди.

3⃣Проверка на пустоту: Для метода empty() верните результат проверки, является ли стек s1 пустым.

😎 Решение:

class MyQueue {
    private var s1: [Int] = []
    private var s2: [Int] = []
    private var front: Int = 0

    func push(_ x: Int) {
        if s1.isEmpty {
            front = x
        }
        while !s1.isEmpty {
            s2.append(s1.removeLast())
        }
        s2.append(x)
        while !s2.isEmpty {
            s1.append(s2.removeLast())
        }
    }

    func pop() -> Int {
        let res = s1.removeLast()
        if !s1.isEmpty {
            front = s1.last!
        }
        return res
    }

    func empty() -> Bool {
        return s1.isEmpty
    }

    func peek() -> Int {
        return front
    }
}

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

Задача: 935. Knight Dialer
Сложность: medium

Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке).


Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 10

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

1⃣Определить возможные движения коня с каждой цифровой клетки.
Использовать динамическое программирование для хранения количества способов достижения каждой цифровой клетки на каждом шаге.

2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1).
На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня.

3⃣Вернуть сумму всех значений в массиве DP на последнем шаге.

😎 Решение:

var knightDialer = function(n) {
    const MOD = 10**9 + 7;
    const moves = {
        0: [4, 6],
        1: [6, 8],
        2: [7, 9],
        3: [4, 8],
        4: [0, 3, 9],
        5: [],
        6: [0, 1, 7],
        7: [2, 6],
        8: [1, 3],
        9: [2, 4]
    };
    
    let dp = new Array(10).fill(1);
    
    for (let step = 1; step < n; step++) {
        const newDp = new Array(10).fill(0);
        for (let i = 0; i < 10; i++) {
            for (const move of moves[i]) {
                newDp[move] = (newDp[move] + dp[i]) % MOD;
            }
        }
        dp = newDp;
    }
    
    return dp.reduce((acc, val) => (acc + val) % MOD, 0);
};

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

Задача: 135. Candy
Сложность: hard

В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings.

Вы раздаете конфеты этим детям с соблюдением следующих требований:

Каждый ребенок должен получить как минимум одну конфету.
Дети с более высоким рейтингом должны получать больше конфет, чем их соседи.
Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей.

Пример:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

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

1⃣Инициализация и первичное заполнение массивов:
Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете.

2⃣Обход и обновление значений в массивах:
Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа.
Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа.

3⃣Расчет минимального количества конфет:
Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет.
Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил.

😎 Решение:

func candy(_ ratings: [Int]) -> Int {
    let len = ratings.count
    var sum = 0
    var left2right = Array(repeating: 1, count: len)
    var right2left = Array(repeating: 1, count: len)

    for i in 1..<len {
        if ratings[i] > ratings[i - 1] {
            left2right[i] = left2right[i - 1] + 1
        }
    }
    for i in stride(from: len - 2, through: 0, by: -1) {
        if ratings[i] > ratings[i + 1] {
            right2left[i] = right2left[i + 1] + 1
        }
    }
    for i in 0..<len {
        sum += max(left2right[i], right2left[i])
    }
    return sum
}

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

Задача: 673. Number of Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Объявите два массива динамического программирования length и count, и инициализируйте их значениями length[i]=1 и count[i]=1. Итерируйте i от 0 до n−1. Для каждого i итерируйте j от 0 до i−1 и, если nums[j] < nums[i], обновите length[i] и count[i] в зависимости от значений length[j] и count[j].

2⃣Найдите максимальное значение в массиве length и сохраните его в переменной maxLength. Инициализируйте переменную result = 0.

3⃣Итерируйте i от 0 до n−1 и, если length[i] = maxLength, добавьте count[i] к result. Верните result.

😎 Решение:

class Solution {
    func findNumberOfLIS(_ nums: [Int]) -> Int {
        let n = nums.count
        var length = Array(repeating: 1, count: n)
        var count = Array(repeating: 1, count: n)
        
        for i in 0..<n {
            for j in 0..<i {
                if nums[j] < nums[i] {
                    if length[j] + 1 > length[i] {
                        length[i] = length[j] + 1
                        count[i] = 0
                    }
                    if length[j] + 1 == length[i] {
                        count[i] += count[j]
                    }
                }
            }
        }
        
        let maxLength = length.max() ?? 0
        var result = 0
        
        for i in 0..<n {
            if length[i] == maxLength {
                result += count[i]
            }
        }
        
        return result
    }
}

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

Задача: 667. Beautiful Arrangement II
Сложность: medium

Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:

Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.

Пример:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

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

1⃣Инициализация списка:
Начните с создания списка от 1 до n: [1, 2, 3, ..., n].

2⃣Конструирование шаблона с k различиями:
Для обеспечения k различных значений разностей используйте следующий подход:
Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.
Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.

3⃣Заполнение списка:
Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.

😎 Решение:

func constructArray(_ n: Int, _ k: Int) -> [Int] {
    var answer = [Int]()
    var left = 1, right = n
    
    for i in 0...k {
        if i % 2 == 0 {
            answer.append(left)
            left += 1
        } else {
            answer.append(right)
            right -= 1
        }
    }
    
    if k % 2 == 0 {
        answer += left...right
    } else {
        answer += (left...right).reversed()
    }
    
    return answer
}

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

Задача: 312. Burst Balloons
Сложность: hard

Дано n воздушных шаров, пронумерованных от 0 до n - 1. Каждый шарик окрашен в число, представленное массивом nums. Вам нужно лопнуть все шарики.

Если вы лопаете шарик i, вы получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если i - 1 или i + 1 выходит за границы массива, то считайте, что там находится шарик с числом 1.

Верните максимальное количество монет, которое можно собрать, лопая шарики с умом.

Пример:

Input: nums = [1,5]
Output: 10

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

1⃣Инициализация и подготовка данных
Добавьте по одному шару с числом 1 в начало и конец массива nums, чтобы упростить обработку граничных случаев. Определите функцию dp(left, right), которая будет возвращать максимальное количество монет, если лопнуть все шары на интервале [left, right] включительно.

2⃣Вычисление значений для всех интервалов
Для каждого интервала [left, right] и каждого индекса i в этом интервале: Вычислите максимальные монеты, которые можно получить, сначала лопая все шары кроме i, а затем лопая i. Обновите dp(left, right) максимальной суммой этих монет.

3⃣Возврат результата
Верните значение dp(1, n - 2), которое будет содержать максимальное количество монет, которое можно собрать, лопнув все шары с умом, исключая добавленные нами шары.

😎 Решение:

class Solution {
    func maxCoins(_ nums: [Int]) -> Int {
        var nums = [1] + nums + [1]
        let n = nums.count
        var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
        
        for length in 2..<n {
            for left in 0..<(n - length) {
                let right = left + length
                for i in (left + 1)..<right {
                    dp[left][right] = max(dp[left][right],
                                          nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right])
                }
            }
        }
        
        return dp[0][n - 1]
    }
}

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