title
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 weightxis totally destroyed, and the stone of weightyhas new weighty-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 <= 301 <= stones[i] <= 100
solution
/**
This question eaquals to partition an array into 2 subsets whose difference is minimal
(1) S1 + S2 = S
(2) S1 - S2 = diff
==> -> diff = S - 2 * S2 ==> minimize diff equals to maximize S2
Now we should find the maximum of S2 , range from 0 to S / 2, using dp can solve this
dp[i][j] = {true if some subset from 1st to j'th has a sum equal to sum i, false otherwise}
i ranges from (sum of all elements) {1..n}
j ranges from {1..n}
same as 494. Target Sum
*/
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
totalSum = sum(stones)
dp = [False for _ in range(totalSum // 2 + 1)]
dp[0] = True
s2 = 0
for stone in stones:
for i in range(totalSum // 2, -1, -1):
dp[i] = dp[i] or (dp[i - stone] if i >= stone else False)
if dp[i]:
s2 = max(s2, i)
return totalSum - 2 * s2