1049. Last Stone Weight II

You are given an array of integers stones where stones[i] is the weight of the $i^{th}$ stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.
 

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that’s the optimal value.

Example 2:

Input: stones = [31,26,33,21,40]
Output: 5

Constraints:

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

From: LeetCode
Link: 1049. Last Stone Weight II

Solution:

Ideas:

• This problem becomes splitting stones into two groups whose sums are as close as possible.
• If one group sums to s1 and the other to s2, final answer is abs(s1 - s2).
• Since s1 + s2 = sum, we just try to get one group as close as possible to sum / 2.
• dp[j] stores the largest achievable sum not exceeding j.

Code:

int lastStoneWeightII(int* stones, int stonesSize) {
    int sum = 0;
    for (int i = 0; i < stonesSize; i++) {
        sum += stones[i];
    }

    int target = sum / 2;
    int dp[1501] = {0};  // max sum is 30 * 100 = 3000, so target <= 1500

    for (int i = 0; i < stonesSize; i++) {
        int w = stones[i];
        for (int j = target; j >= w; j--) {
            int candidate = dp[j - w] + w;
            if (candidate > dp[j]) {
                dp[j] = candidate;
            }
        }
    }

    return sum - 2 * dp[target];
}