1049. Last Stone Weight II

Practice Last Stone Weight II for free on NudgeCode: Medium, Dynamic Programming pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

You have stones with weights stones. Repeatedly pick any two stones and smash them together: if they weigh x <= y, both are destroyed when x == y, otherwise a stone of weight y - x remains. Continue until at most one stone is left. Return the smallest possible weight of the final stone (0 if none remain).

Example

stones = [2,7,4,1,8,1]      ->  1
stones = [31,26,33,21,40]   ->  5

Constraints

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100