Участник:Easik/last-stone-weight-ii

Материал из DISCOPAL
Перейти к: навигация, поиск

Python

class Solution(object):
    def lastStoneWeightII(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
 
        dp = {0}
        total_weight = sum(stones)
 
        # Smash rocks
        for stone in stones:
            dp = dp | {stone + i for i in dp}
 
        # Smallest possible weight of left stone
        min_res = min(abs(total_weight - i - i) for i in dp)
 
        return min_res