We have a collection of rocks, each rock has a positive integer weight.
Each turn, we choose any two rocks and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)
 
Example 1:
Input: [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.

 
Note:

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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        

Solutions:
class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		dp = {0}
		total = sum(stones)
		for stone in stones:
			dp |= {_sum + stone for _sum in dp}
		return min((abs(total - _sum - _sum) for _sum in dp))


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		res = set()
		res.add(stones[0])
		for n in stones[1:]:
			newres = set()
			for m in res:
				newres.add(n + m)
				newres.add(abs(n - m))
			res = newres
		return min(res)


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:

		def dp(i, j):
			if i == N:
				return j
			if (i, j) in memo:
				return memo[i, j]
			memo[i, j] = min(dp(i + 1, abs(j + stones[i])), dp(i + 1, abs(j - stones[i])))
			return memo[i, j]
		memo = {}
		N = len(stones)
		return dp(0, 0)


class Solution:

	def lastStoneWeightII(self, arr: List[int]) -> int:
		upperBound = sum(arr) // 2
		dp = [[0 for i in range(upperBound + 1)] for j in range(len(arr))]
		for i in range(len(dp)):
			for j in range(len(dp[0])):
				if arr[i] <= j:
					dp[i][j] = max(dp[i - 1][j - arr[i]] + arr[i], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return sum(arr) - 2 * dp[-1][-1]


from functools import lru_cache

class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		n = len(stones)
		if n == 1:
			return stones[0]

		@lru_cache(None)
		def dfs(index, curSum):
			if index == n:
				return abs(curSum)
			return min(dfs(index + 1, curSum + stones[index]), dfs(index + 1, curSum - stones[index]))
		return dfs(0, 0)


import queue

class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		total = sum(stones)
		return self.topDown(stones, 0, 0, 0, [[None for s in range(total + 1)] for i in range(len(stones))])

	def topDown(self, stones, idx, sum1, sum2, memo):
		if idx >= len(stones):
			return abs(sum1 - sum2)
		if memo[idx][sum1] != None:
			return memo[idx][sum1]
		difference_1 = self.topDown(stones, idx + 1, sum1 + stones[idx], sum2, memo)
		difference_2 = self.topDown(stones, idx + 1, sum1, sum2 + stones[idx], memo)
		memo[idx][sum1] = min(difference_1, difference_2)
		return memo[idx][sum1]


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		mem = {}

		def explore(a, b, stones):
			if len(stones) == 0:
				return abs(a - b)
			entry = (a, b, len(stones))
			if entry in mem:
				return mem[entry]
			s = stones.pop()
			m = min(explore(a + s, b, stones), explore(a, b + s, stones))
			stones.append(s)
			mem[entry] = m
			return m
		return explore(0, 0, stones)

	def lastStoneWeightIITLE(self, stones: List[int]) -> int:
		N = len(stones)
		if not stones:
			return 0
		if N == 1:
			return stones[0]
		if N == 2:
			return abs(stones[0] - stones[1])
		out = float('inf')
		for i in range(N):
			for j in range(i + 1, N):
				right = stones.pop(j)
				left = stones.pop(i)
				diff = abs(right - left)
				out = min(out, self.lastStoneWeightII(stones + [diff]))
				stones.insert(i, left)
				stones.insert(j, right)
		return out


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		cache = {}

		def diffs(s1: int, s2: int, xs: List[int]) -> int:
			if len(xs) == 0:
				return abs(s1 - s2)
			if (s1, s2, len(xs)) not in cache:
				y = xs.pop()
				min_val = min(diffs(s1 + y, s2, xs), diffs(s1, s2 + y, xs))
				xs.append(y)
				cache[s1, s2, len(xs)] = min_val
			return cache[s1, s2, len(xs)]
		return diffs(stones[0], 0, stones[1:])


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		total = sum(stones)
		target = total // 2
		dp = [0] * (target + 1)
		for stone in stones:
			for i in range(target, stone - 1, -1):
				dp[i] = max(dp[i], dp[i - stone] + stone)
		return total - 2 * dp[-1]


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:

		def helper(i, currSum):
			if i == len(stones):
				return abs(total - 2 * currSum)
			if (i, currSum) in cache:
				return cache[i, currSum]
			takeIt = helper(i + 1, currSum + stones[i])
			ignoreIt = helper(i + 1, currSum)
			cache[i, currSum] = min(takeIt, ignoreIt)
			return cache[i, currSum]
		cache = {}
		total = sum(stones)
		return helper(0, 0)


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		self.dp = {}

		def helper(index, total):
			if index == len(stones):
				return abs(total)
			if (index, total) in self.dp:
				return self.dp[index, total]
			self.dp[index, total] = min(helper(index + 1, total + stones[index]), helper(index + 1, total - stones[index]))
			return self.dp[index, total]
		return helper(0, 0)


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		n = len(stones)
		total = sum(stones)
		memo = {}

		def dp(i, t):
			if (i, t) in memo:
				return memo[i, t]
			if i == -1:
				memo[i, t] = t == 0
			elif t < 0:
				memo[i, t] = False
			else:
				memo[i, t] = dp(i - 1, t) or dp(i - 1, t - stones[i])
			return memo[i, t]
		return min((abs(total - 2 * t) for t in range(total // 2 + 1) if dp(n - 1, t)))


from heapq import heapify, heappush, heappop

class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		arr = stones
		n = len(stones)
		su = sum(arr)
		dp = [[0 for i in range(su + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for j in range(1, n + 1):
			for i in range(1, su + 1):
				dp[j][i] = dp[j - 1][i]
				if i - arr[j - 1] >= 0:
					dp[j][i] |= dp[j - 1][i - arr[j - 1]]
		diff = sys.maxsize
		for j in range(su // 2, -1, -1):
			if dp[n][j] == True:
				diff = su - 2 * j
				break
		return diff


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		from functools import lru_cache

		@lru_cache(None)
		def helper(ind, curr):
			if ind == len(stones):
				return abs(curr)
			return min(helper(ind + 1, curr + stones[ind]), helper(ind + 1, curr - stones[ind]))
		return helper(0, 0)


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		mem = {}

		def explore(a, b, stones):
			if len(stones) == 0:
				return abs(a - b)
			entry = (a, b, len(stones))
			if entry in mem:
				return mem[entry]
			s = stones.pop()
			m = min(explore(a + s, b, stones), explore(a, b + s, stones))
			stones.append(s)
			mem[entry] = m
			return m
		return explore(0, 0, stones)


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		n = len(stones)
		total = sum(stones)
		diff = total
		dp = [[False] * (1 + total) for _ in range(1 + n)]
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, n + 1):
			s = stones[i - 1]
			for j in range(1, 1 + total):
				if j < s:
					dp[i][j] = dp[i - 1][j]
					continue
				dp[i][j] = dp[i - 1][j] or dp[i - 1][j - s]
				if dp[i][j]:
					diff = min(diff, abs(total - 2 * j))
		return diff


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		dp = {0}
		sum_stones = sum(stones)
		for stone in stones:
			dp |= {stone + i for i in dp}
		return min((abs(sum_stones - i - i) for i in dp))


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		(dp, sumA) = ({0}, sum(stones))
		for a in stones:
			dp = {a + x for x in dp} | {a - x for x in dp}
		return min((abs(x) for x in dp))


from functools import lru_cache

class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		lim = len(stones)

		@lru_cache(None)
		def r(s, i):
			if i == lim - 1:
				return min(s + stones[-1], abs(s - stones[-1]))
			else:
				return min(r(s + stones[i], i + 1), r(abs(s - stones[i]), i + 1))
		return r(0, 0)


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		target = sum(stones)
		target = target // 2
		dp = [[False] * (target + 1) for _ in range(len(stones) + 1)]
		for i in range(len(stones) + 1):
			for j in range(target + 1):
				if j == 0:
					dp[i][j] = True
				elif stones[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - stones[i - 1]] or dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		for j in reversed(range(target + 1)):
			if dp[-1][j]:
				return sum(stones) - 2 * j


class Solution:

	def lastStoneWeightII(self, stones: List[int]) -> int:
		total = sum(stones)
		dp = [[None for _ in range(total // 2 + 1)] for _ in range(len(stones))]
		for num in range(total // 2 + 1):
			if stones[0] <= num:
				dp[0][num] = stones[0]
			else:
				dp[0][num] = 0
		for index in range(1, len(stones)):
			for num in range(total // 2 + 1):
				if stones[index] <= num:
					take = stones[index] + dp[index - 1][num - stones[index]]
					dp[index][num] = max(take, dp[index - 1][num])
				else:
					dp[index][num] = dp[index - 1][num]
		return total - dp[-1][-1] - dp[-1][-1]