You are given an array of integers stones where stones[i] is the weight of the ith 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 weightxis destroyed, and the stone of weightyhas new weighty - 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
Example 3:
Input: stones = [1,2] Output: 1
Constraints:
1 <= stones.length <= 301 <= stones[i] <= 100
This question can be converted to calculate how many stones a backpack with a capacity of sum / 2 can hold.
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
s = sum(stones)
n = s // 2
dp = [False for i in range(n + 1)]
dp[0] = True
for stone in stones:
for j in range(n, stone - 1, -1):
dp[j] = dp[j] or dp[j - stone]
for j in range(n, -1, -1):
if dp[j]:
return s - j - jclass Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int stone : stones) {
sum += stone;
}
int n = sum / 2;
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int stone : stones) {
for (int j = n; j >= stone; j--) {
dp[j] = dp[j] || dp[j - stone];
}
}
for (int j = n; ; j--) {
if (dp[j]) {
return sum - j - j;
}
}
}
}func lastStoneWeightII(stones []int) int {
sum := 0
for _, stone := range stones {
sum += stone
}
n := sum / 2
dp := make([]bool, n+1)
dp[0] = true
for _, stone := range stones {
for j := n; j >= stone; j-- {
dp[j] = dp[j] || dp[j-stone]
}
}
for j := n; ; j-- {
if dp[j] {
return sum - j - j
}
}
}