1. Problem Overview

We are given an array stones[i] representing weights. Each turn:

• Pick two stones x ≤ y

• if x == y: both vanish

• else: new stone = y - x

At most one stone remains.
Return the smallest possible final weight.

Example:

Input:  [2,7,4,1,8,1]
Output: 1

Constraints:

• length ≤ 30

• weight ≤ 100

• total sum ≤ 3000 → perfect for knapsack-style DP

---

2. Initial Understanding (Partition Insight)

The key insight:

The final remaining weight equals the difference between two subsets
whose sums are as close as possible.

Let the total sum be:

S = sum(stones)

Let one subset’s sum be x, the other S - x.
The final result is:

|x - (S - x)| = |2x - S|

To minimize this, we want:

choose subset sum x as close to S/2 as possible.

This is precisely a 0-1 knapsack problem:

• Capacity = target = S / 2

• Weight = stone weight

• Value = stone weight

• Goal = maximize subset sum ≤ target

Once we get:

best = maximum subset sum <= target

The answer is:

S - 2 * best

---

3. Why the Formula Is Always Non-Negative

Some might think the formula needs an absolute value, but it does not:

S - 2 * best >= 0

Because:

• best ≤ target = S/2

• ⇒ 2*best ≤ S

• ⇒ S - 2*best ≥ 0

So the final expression never goes negative.
No abs() needed.

---

4. 2D DP vs 1D DP

You can solve this with a 2D DP dp[i][j], but it’s unnecessary.

The classic optimized form uses a 1D DP array:

dp[j] = maximum subset sum with capacity j

To respect 0-1 knapsack rules, we iterate j from high → low.

---

5. Why the DP Array Must Be target + 1

This is a subtle but important detail.

We need to model capacities:

0, 1, 2, ..., target

That is target + 1 states.

Example:
If target = 5, we must access:

dp[0], dp[1], dp[2], dp[3], dp[4], dp[5]

Thus:

int[] dp = new int[target + 1];

If we mistakenly used:

new int[target]; // WRONG

We lose access to dp[target], causing out-of-bounds or wrong results.

---

6. Final 1D DP Solution (Optimized and Clean)

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum / 2;

        // dp[j] = maximum subset sum achievable with capacity j
        int[] dp = new int[target + 1];

        for (int stone : stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        }

        return sum - 2 * dp[target];
    }
}

Complexity

• Time: O(n target) ≈ O(30 1500)

• Space: O(target)

7. Key Takeaways

This is a partition problem disguised as a stone-smashing game

Turning it into |2x - S| makes the DP structure obvious.

The correct DP is classic 0-1 knapsack

Weight = value = stone weight.

Space optimization simplifies the code

1D DP is both clearer and faster.

target + 1 is necessary

Because we need to represent all capacities from 0 to target inclusive.

---

8. Final Thoughts

LeetCode 1049 is a great example of:

• Reformulating a game problem into a math expression

• Reducing that expression to a subset partition

• solving it cleanly via knapsack DP

This problem strengthens intuition for many other DP and knapsack-related interview problems, including:

• LeetCode 416 — Partition Equal Subset Sum

• LeetCode 698 — Partition to K Equal Sum Subsets

• LeetCode 494 — Target Sum