#1049

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Last Stone Weight II

In the 'Last Stone Weight II' problem, you need to find the minimal possible stone weight after a series of smashes using dynamic programming.

array dynamic programming

Problem Statement

You are given an array of integers stones where stones[i] represents the weight of the ith stone. In each step, you pick two stones, x and y (x ≤ y), and smash them together, resulting in a new stone of weight |x - y|. The process continues until one or no stones are left.

The challenge is to determine the smallest possible stone weight left after all possible smashes. The problem involves dynamic programming to consider all possible combinations and track the optimal result. Focus on minimizing the final remaining weight.

Examples

Example 1

Input: stones = [2,7,4,1,8,1]

Output: 1

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.

Example 2

Input: stones = [31,26,33,21,40]

Output: 5

Example details omitted.

Constraints

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

Solution Approach

State Transition Dynamic Programming

Treat the problem as a state transition problem where each state represents a possible weight sum. Use dynamic programming to explore all combinations of adding or subtracting the stone weights from the current sum, ensuring that the smallest possible weight is achieved.

Subset Sum Problem Analogy

Consider this as a variation of the subset-sum problem, where each stone weight can contribute either positively or negatively to the total sum. The goal is to find the smallest absolute difference between the total sums of positive and negative values.

Tracking Possible Outcomes

Use a dynamic programming table to track possible sums during the stone pairing process. For each stone, update the set of achievable sums and ensure the smallest possible final weight is selected.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexities depend on the dynamic programming approach used. In the worst case, with 30 stones and each stone weighing up to 100, the approach must manage the sum range and the number of possible states. The time complexity can range from O(n * sum) to O(n^2), while space complexity may vary depending on how states are tracked.

What Interviewers Usually Probe

Candidate understands dynamic programming and state transitions.
Able to relate the problem to the subset-sum pattern with both addition and subtraction.
Can efficiently optimize the solution by tracking achievable states and minimizing the result.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle negative weights and possible sum ranges.
Not considering all possible combinations of pairings during the stone smash process.
Overcomplicating the problem by trying to brute force every possible combination without using dynamic programming.

Follow-up variants

Increasing the number of stones to test the scalability of the approach.
Allowing negative weights for stones to introduce more complexity in the calculations.
Introducing additional constraints, such as limiting the number of smashes or requiring a specific stone pairing order.

FAQ

What is the approach to solve the Last Stone Weight II problem?

The problem is best approached using dynamic programming, where you track the possible sums of stone weights with addition and subtraction to minimize the final result.

How does state transition dynamic programming help in this problem?

State transition dynamic programming allows you to explore all possible outcomes of each stone pairing, ensuring the smallest weight remains at the end by tracking feasible sum combinations.

What is the time complexity of the solution for Last Stone Weight II?

The time complexity depends on the number of stones and their weights, generally ranging from O(n * sum) to O(n^2), based on the dynamic programming approach used.

Can negative weights be involved in the Last Stone Weight II problem?

While the problem as stated only involves positive weights, the dynamic programming approach can be adapted to handle negative weights if the problem were modified.

How can I optimize my solution for Last Stone Weight II?

Focus on reducing the number of states to track, making use of efficient data structures to manage achievable sums and minimizing redundant calculations in the dynamic programming table.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        s = sum(stones)
        m, n = len(stones), s >> 1
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(n + 1):
                dp[i][j] = dp[i - 1][j]
                if stones[i - 1] <= j:
                    dp[i][j] = max(
                        dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]
                    )
        return s - 2 * dp[-1][-1]

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        s = sum(stones)
        m, n = len(stones), s >> 1
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(n + 1):
                dp[i][j] = dp[i - 1][j]
                if stones[i - 1] <= j:
                    dp[i][j] = max(
                        dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]
                    )
        return s - 2 * dp[-1][-1]

Continue Practicing

#1048 longest string chain #1043 partition array for maximum sum #1039 minimum score triangulation of polygon