Сложность: 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), которое будет содержать максимальное количество монет, которое можно собрать, лопнув все шары с умом, исключая добавленные нами шары.
😎 Решение:
public class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] newNums = new int[n + 2];
newNums[0] = 1;
newNums[n + 1] = 1;
System.arraycopy(nums, 0, newNums, 1, n);
int[][] dp = new int[n + 2][n + 2];
for (int length = 2; length < n + 2; length++) {
for (int left = 0; left < n + 2 - length; left++) {
int right = left + length;
for (int i = left + 1; i < right; i++) {
dp[left][right] = Math.max(dp[left][right],
newNums[left] * newNums[i] * newNums[right] + dp[left][i] + dp[i][right]);
}
}
}
return dp[0][n + 1];
}
}Ставь 👍 и забирай 📚 Базу знаний