Сложность: 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]
}
}Ставь 👍 и забирай 📚 Базу знаний