1049. Last Stone Weight II

leetcode medium

#array#csharp#dynamic-programming#leetcode#math#medium

Task

Вам дан массив целых чисел 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

C# solution

matched/original

public class Solution {
    public int LastStoneWeightII(int[] stones) {
        int totalSum = stones.Sum();
        int halfSum = totalSum / 2;
        int[] dp = new int[halfSum + 1];
        foreach (var stone in stones) {
            for (int j = halfSum; j >= stone; j--) {
                dp[j] = Math.Max(dp[j], dp[j - stone] + stone);
            }
        }
        return totalSum - 2 * dp[halfSum];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LastStoneWeightII(vector<int>& stones) {
        int totalSum = stones.Sum();
        int halfSum = totalSum / 2;
        vector<int>& dp = new int[halfSum + 1];
        foreach (var stone in stones) {
            for (int j = halfSum; j >= stone; j--) {
                dp[j] = max(dp[j], dp[j - stone] + stone);
            }
        }
        return totalSum - 2 * dp[halfSum];
    }
}

Java solution

matched/original

public class Solution {
    public int lastStoneWeightII(int[] stones) {
        int totalSum = 0;
        for (int stone : stones) {
            totalSum += stone;
        }
        int halfSum = totalSum / 2;
        int[] dp = new int[halfSum + 1];

        for (int stone : stones) {
            for (int j = halfSum; j >= stone; j--) {
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        }

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

JavaScript solution

matched/original

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];
}

Python solution

matched/original

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]

Explanation

Algorithm

Используй метод динамического программирования, чтобы проверить, можно ли разделить камни на две группы с равной суммой.

Определи, какие веса можно достичь, используя половину суммы всех камней.

Найди наибольшую достижимую сумму, которая меньше или равна половине общей суммы, и верни разницу между общей суммой и удвоенной этой суммой.Верни максимальную длину среди всех цепочек.

😎