Сложность: 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⃣Найди наибольшую достижимую сумму, которая меньше или равна половине общей суммы, и верни разницу между общей суммой и удвоенной этой суммой.Верни максимальную длину среди всех цепочек.
😎 Решение:
def lastStoneWeightII(stones):
total_sum = sum(stones)
half_sum = total_sum // 2
dp = [0] * (half_sum + 1)
for stone in stones:
for j in range(half_sum, stone - 1, -1):
dp[j] = max(dp[j], dp[j - stone] + stone)
return total_sum - 2 * dp[half_sum]
Ставь 👍 и забирай 📚 Базу знаний