Задача: 1049. Last Stone Weight II
Сложность: 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) {
    $totalSum = array_sum($stones);
    $halfSum = intdiv($totalSum, 2);
    $dp = array_fill(0, $halfSum + 1, 0);

    foreach ($stones as $stone) {
        for ($j = $halfSum; $j >= $stone; $j--) {
            $dp[$j] = max($dp[$j], $dp[$j - $stone] + $stone);
        }
    }

    return $totalSum - 2 * $dp[$halfSum];
}

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