Last Stone Weight II

Problem Statement

Given an array of integers stones where stone[i] represents the weight of the ith stone. You want to play a game where you smash stones together. The rules are, for any two stones i,j in the array:

1. If stones[i] == stones[j], both get destroyed.
2. If stones[i] > stones[j], then stones[j] gets removed and stones[i] -= stones[j].

Return the smallest stone weight you can achieve with this game. Note that you can have at most one remaining stone in your final array, meaning you can either smash all of them together or have one remaining smallest stone.

Solution

Keyword: smallest. This is an immediate signal for DP as we need to make the best decision at every step. For the sake of learning, just imagine what would happen if you originally tried doing something greedy and tried to, say, choose the closest stones in weight every turn. Its trivial to see that this would not be optimal. Consider these weights: [100, 99, 2, 1]. A greedy algorithm is completely defeated by this. I digress.

What do we notice about this? Well go and read Partition Equal Subset Sum and come back if nothing is sticking out to you. Alright... isn't this just the same problem where we want to partition into two subsets that offset each other as close as possible? It is hard to really think about this in a different way to justify Knapsack DP, because, in the traditional sense, there is no constraint listed in the problem. However, as mentioned above, a mental reframing of what we are trying to achieve can be the missing piece.

So here is the reframed problem statement: find the closest subset sums that divide the stones up and return the difference between the closest subsets. How do we solve this new problem? What states can we track? Perhaps a better question to start out with is: how do you build from the ground up.

Let dp[i] represent the maximum achievable sum not exceeding sum(stones) // 2. We can find the subset that comes closest to half of the sum and apply complementary logic to find our answer.

total = sum(stones)
target = total // 2
dp = [False] * (target+1)
dp[0] = True

for s in stones:
	for v in range(target, s-1, -1):
		dp[v] = dp[v] or dp[v - s]

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

• Runtime Complexity: O(n)
• Space Complexity: O(max(n)//2)