Сложность: medium
Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.
Пример:
Input: stones = [2,7,4,1,8,1]
Output: 1
👨💻 Алгоритм:
1⃣Используй метод динамического программирования, чтобы проверить, можно ли разделить камни на две группы с равной суммой.
2⃣Определи, какие веса можно достичь, используя половину суммы всех камней.
3⃣Найди наибольшую достижимую сумму, которая меньше или равна половине общей суммы, и верни разницу между общей суммой и удвоенной этой суммой.Верни максимальную длину среди всех цепочек.
😎 Решение:
func lastStoneWeightII(_ stones: [Int]) -> Int {
let totalSum = stones.reduce(0, +)
let halfSum = totalSum / 2
var dp = Array(repeating: 0, count: halfSum + 1)
for stone in stones {
for j in stride(from: halfSum, through: stone, by: -1) {
dp[j] = max(dp[j], dp[j - stone] + stone)
}
}
return totalSum - 2 * dp[halfSum]
}Ставь 👍 и забирай 📚 Базу знаний