323. Last Stone Weight II
MediumDynamic Programming
You are given an array of integers stones where stones[i] is the weight of the i-th 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; if x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - 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.
Examples
Input: [2,7,4,1,8,1]
Output: 1
Explanation: Best split gives sums 11 and 12; difference 1.
Constraints
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 100
Loading...
Run checks all cases above. Submit evaluates all test cases.