Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1049.html

1049. Last Stone Weight II

Level

Medium

Description

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose any two rocks 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 totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)

Example 1:

Input: [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.

Note:

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

Solution

This problem is equivalent to splitting the array stones into two parts such that the sums of two parts have the minimum absolute difference. The capacity of the first part is half the sum of all the stones. This can be solved using dynamic programming.

For each stone, there are two choices, which are to select the stone in the first part or not to select the stone in the first part. If the stone is not selected, then the sum is the same as the previous state (when considering the previous stone). If the stone is selected, then the total sum after selecting the stone must not exceed the capacity, and in this case, calculate the total sum and update the maximum sum possible.

After the maximum sum of the first part is calculated, the sum of the second part can also be calculated, and return the absolute difference between the two parts’ sums.

  • class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones)
            sum += stone;
        int length = stones.length;
        int capacity = sum / 2;
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < length; i++) {
            int stone = stones[i];
            for (int j = capacity; j >= stone; j--)
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
        }
        int maxSum = dp[capacity];
        int remaining = sum - maxSum;
        return Math.abs(maxSum - remaining);
    }
}

  • // OJ: https://leetcode.com/problems/last-stone-weight-ii/
// Time: O(N + SUM(A))
// Space: O(SUM(A))
// Ref: https://leetcode.com/problems/last-stone-weight-ii/discuss/294888/JavaC%2B%2BPython-Easy-Knapsacks-DP
class Solution {
public:
    int lastStoneWeightII(vector<int>& A) {
        bitset<1501> dp = {1};
        int sum = 0;
        for (int a : A) {
            sum += a;
            for (int i = min(1500, sum); i >= a; --i) {
                dp[i] = dp[i] + dp[i - a];
            }
        }
        for (int i = sum / 2; i >= 0; --i) {
            if (dp[i]) return sum - i - i;
        }
        return 0;
    }
};

  • class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        s = sum(stones)
        m, n = len(stones), s >> 1
        dp = [0] * (n + 1)
        for v in stones:
            for j in range(n, v - 1, -1):
                dp[j] = max(dp[j], dp[j - v] + v)
        return s - dp[-1] * 2



  • func lastStoneWeightII(stones []int) int {
	s := 0
	for _, v := range stones {
		s += v
	}
	n := s >> 1
	dp := make([]int, n+1)
	for _, v := range stones {
		for j := n; j >= v; j-- {
			dp[j] = max(dp[j], dp[j-v]+v)
		}
	}
	return s - dp[n]*2
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

  • /**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function (stones) {
    let s = 0;
    for (let v of stones) {
        s += v;
    }
    const n = s >> 1;
    let dp = new Array(n + 1).fill(0);
    for (let v of stones) {
        for (let j = n; j >= v; --j) {
            dp[j] = Math.max(dp[j], dp[j - v] + v);
        }
    }
    return s - dp[n] * 2;
};

All Problems

All Solutions