Last Stone Weight II

LeetCode Q 1049 - Last Stone Weight II

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 <= stones.length <= 30
• 1 <= stones[i] <= 100

Similar Question: leetcodeQ494

Solution

This question can be transferred to finding the maximum sum (S2) of some stones providing S2 is no more than the total sum (sum) of all stones. Next, we will explain why this transfer works?

Suppose we have four stones a, b, c, d. We have the following choices:

• smath a, b and c, d, then get two new stones a - b and c - d; smath them we have (a - b) - (c - d) = (a + d) - (b + c).
• smath a, b, get a - b; smath it with c, get a - b - c; smath it with d, get a - b - c - d = a - (b + c + d).
  …

We can see what we actrually do is splitting stones into two groups, and smath them. Suppose we have two groups S1 and S2, then we have
S1 + S2 = sum
S1 - S2 = res
Therefore,
sum - 2 * S2 = res
We want to get the minimum possible value of res, S2 should be as large as possible and at the same time S2 <= sum / 2.

Code:

public int lastStoneWeightII(int[] stones) {
  int sum = 0;
  for (int stone: stones) sum += stone;

  int num = stones.length;
  boolean[][] dp = new boolean[num + 1][sum + 1];
  
  for (int i = 0; i <= num; i++) dp[0][i] = true;

  int S2 = 0;
  for (int i = 1; i <= num; i++) {
    for (int s = 1; s <= sum / 2; s++) {
      if (dp[i - 1][s] || (s >= stones[i - 1] && dp[i - 1][s - stones[i - 1]])) {
      	dp[i][s] = true;
      	S2 = Math.max(S2, s);
      }
    }
  }

  return sum - S2;
}