All problems

Last Stone Weight II

Medium · dynamic programming

You have a pile of stones, where stones[i] is the weight of stone i.

While two or more stones remain, you must pick any two of them and smash them together:

• If they weigh the same, both are destroyed.
• Otherwise the lighter one is destroyed, and the heavier one stays with its weight reduced by the weight of the lighter one.

You choose which two stones to smash at every step. Return the smallest possible weight the last stone can have. If every stone ends up destroyed, return 0.

Examples

Example 1

Input: stones = [6, 4, 3, 3]

Output: 2

Smash 6 with 4 to leave a 2, and smash the two 3s together. The 2 is all that remains.

Example 2

Input: stones = [5]

Output: 5

With a single stone there is nothing to smash, so it stays at 5.

Example 3

Input: stones = [4, 4, 8]

Output: 0

Smash 4 with 8 to leave a 4, then smash that 4 with the other 4. Nothing is left.

Constraints

• 1 <= len(stones) <= 50
• 1 <= stones[i] <= 100