1049.-last-stone-weight-ii.md

1049. Last Stone Weight II

## 等价于最靠近 sum一半的最大值

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        sumv = sum(stones)
        sumv //= 2
        n = len(stones)
        f = [[0] * (sumv + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            for j in range(sumv + 1):
                ## 
                f[i][j] = f[i - 1][j]
                if j >= stones[i - 1]:
                    f[i][j] = max(f[i][j], f[i - 1][j - stones[i - 1]] + stones[i - 1])

        return sum(stones) - f[n][sumv] - f[n][sumv]