Задача: 1000. Minimum Cost to Merge Stones
Сложность: 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 {
    func mergeStones(_ stones: [Int], _ k: Int) -> Int {
        let n = stones.count
        if (n - 1) % (k - 1) != 0 {
            return -1
        }

        var prefix = [Int](repeating: 0, count: n + 1)
        for i in 0..<n {
            prefix[i + 1] = prefix[i] + stones[i]
        }

        var dp = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)
        for m in stride(from: k, through: n, by: 1) {
            for i in 0...n - m {
                let j = i + m - 1
                dp[i][j] = Int.max
                for t in stride(from: i, to: j, by: k - 1) {
                    dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j])
                }
                if (j - i) % (k - 1) == 0 {
                    dp[i][j] += prefix[j + 1] - prefix[i]
                }
            }
        }

        return dp[0][n - 1]
    }
}

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