Last Stone Weight II Python Solution

lcpy gen -n 1049   # by problem number
lcpy gen -s last_stone_weight_ii   # by problem name

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.

Input: stones = [31,26,33,21,40]
Output: 5

class Solution:
    # Time: O(n * total)
    # Space: O(total)
    def last_stone_weight_ii(self, stones: list[int]) -> int:
        total = sum(stones)
        target = total // 2

        # reachable[s] = True if a subset sums to s.
        reachable = [False] * (target + 1)
        reachable[0] = True

        for stone in stones:
            for s in range(target, stone - 1, -1):
                if reachable[s - stone]:
                    reachable[s] = True

        for s in range(target, -1, -1):
            if reachable[s]:
                return total - 2 * s
        return total