Last Stone Weight II LeetCode solution in Python

1
class Solution:
2
    def lastStoneWeightII(self, stones: List[int]) -> int:
3
        if len(stones) == 1:
4
            return stones[0]
5
        total = sum(stones)
6
        half, leng = total // 2, len(stones)
7
        dp = [[0] * (half + 1) for _ in range(leng + 1)]
8

9
        for i in range(1, leng + 1):
10
            for j in range(1, half + 1):
11
                if j - stones[i - 1] >= 0:
12
                    dp[i][j] = max(
13
                        dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]
14
                    )
15
                else:
16
                    dp[i][j] = dp[i - 1][j]
17
        return total - 2 * dp[leng][half]