Сложность: hard
Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.
Пример:
Input: stones = [3,2,4,1], k = 2
Output: 20
👨💻 Алгоритм:
1⃣Проверка на возможность объединения:
Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1.
2⃣Инициализация и динамическое программирование:
Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней.
Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве.
3⃣Заполнение таблицы dp:
Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование.
Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения.
😎 Решение:
class Solution:
def mergeStones(self, stones: List[int], k: int) -> int:
n = len(stones)
if (n - 1) % (k - 1) != 0:
return -1
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + stones[i]
dp = [[0] * n for _ in range(n)]
for m in range(k, n + 1):
for i in range(n - m + 1):
j = i + m - 1
dp[i][j] = min(dp[i][t] + dp[t + 1][j] for t in range(i, j, k - 1))
if (j - i) % (k - 1) == 0:
dp[i][j] += prefix[j + 1] - prefix[i]
return dp[0][n - 1]
Ставь 👍 и забирай 📚 Базу знаний