Сложность: 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⃣Найди наибольшую достижимую сумму, которая меньше или равна половине общей суммы, и верни разницу между общей суммой и удвоенной этой суммой.Верни максимальную длину среди всех цепочек.
😎 Решение:
function lastStoneWeightII(stones) {
const totalSum = stones.reduce((a, b) => a + b, 0);
const halfSum = Math.floor(totalSum / 2);
const dp = Array(halfSum + 1).fill(0);
for (let stone of stones) {
for (let j = halfSum; j >= stone; j--) {
dp[j] = Math.max(dp[j], dp[j - stone] + stone);
}
}
return totalSum - 2 * dp[halfSum];
}Ставь 👍 и забирай 📚 Базу знаний