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 weightx
is totally destroyed, and the stone of weighty
has new weightyx
.
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 <= stones.length <= 30
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/laststoneweightii/ // Time: O(N + SUM(A)) // Space: O(SUM(A)) // Ref: https://leetcode.com/problems/laststoneweightii/discuss/294888/JavaC%2B%2BPythonEasyKnapsacksDP 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[jv]+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; };