Compute the total sum of stones (23) and calculate half (11) to limit the DP array size.
💡 Focusing on sums up to half the total is key because the problem reduces to partitioning stones into two groups with minimal difference.
Line:total = sum(stones)
half = total // 2
💡 The problem transforms into finding a subset of stones with sum as close as possible to half the total.
setup
Initialize DP array with dp[0] = True
Initialize a boolean DP array of size half+1 (12) with dp[0] set to True, meaning sum 0 is always achievable.
💡 Starting with dp[0] = True establishes the base case: zero sum is achievable with no stones.
Line:dp = [False] * (half + 1)
dp[0] = True
💡 This initialization sets the foundation for building achievable sums incrementally.
fill_cells
Process stone 0 with weight 2
Process the first stone (weight 2), iterating sums backwards from 11 down to 2 to update achievable sums.
💡 Backward iteration prevents using the same stone multiple times in one iteration and updates sums achievable by including this stone.
Line:for w in range(half, weight - 1, -1):
dp[w] = dp[w] or dp[w - weight]
💡 dp[2] becomes True because dp[0] was True, meaning sum 2 is now achievable.
fill_cells
Process stone 1 with weight 7
Process the second stone (weight 7), updating dp from 11 down to 7.
💡 Including stone 7 expands achievable sums by adding 7 to previously achievable sums.
Line:for w in range(half, weight - 1, -1):
dp[w] = dp[w] or dp[w - weight]
💡 dp[7] and dp[9] become True because dp[0] and dp[2] were True respectively.
fill_cells
Process stone 2 with weight 4
Process the third stone (weight 4), updating dp from 11 down to 4.
💡 Adding stone 4 allows sums that are 4 more than previously achievable sums.
Line:for w in range(half, weight - 1, -1):
dp[w] = dp[w] or dp[w - weight]
💡 dp[4], dp[6], and dp[11] become True because dp[0], dp[2], and dp[7] were True respectively.
fill_cells
Process stone 3 with weight 1
Process the fourth stone (weight 1), updating dp from 11 down to 1.
💡 Small stones help fill in gaps in achievable sums, increasing granularity.
Line:for w in range(half, weight - 1, -1):
dp[w] = dp[w] or dp[w - weight]
💡 dp[1], dp[5], dp[7], dp[8], and dp[10] become True based on previous dp values.
fill_cells
Process stone 4 with weight 8
Process the fifth stone (weight 8), updating dp from 11 down to 8.
💡 Large stones create new achievable sums by adding to smaller sums.
Line:for w in range(half, weight - 1, -1):
dp[w] = dp[w] or dp[w - weight]
💡 dp[8], dp[9], dp[10], and dp[11] remain or become True based on dp[w-8].
fill_cells
Process stone 5 with weight 1
Process the last stone (weight 1), updating dp from 11 down to 1.
💡 This last stone may fill remaining gaps in achievable sums.
Line:for w in range(half, weight - 1, -1):
dp[w] = dp[w] or dp[w - weight]
💡 dp[3] becomes True, filling a gap and making all sums from 0 to 11 achievable.
traverse
Find largest achievable sum w ≤ half
Scan dp array backwards from 11 down to 0 to find the largest w where dp[w] is True.
💡 Finding this w gives the closest sum to half the total, minimizing the difference.
Line:for w in range(half, -1, -1):
if dp[w]:
return total - 2 * w
💡 The best partition sum is 11, leading to minimal last stone weight difference.
reconstruct
Return final answer
Return the minimal last stone weight difference, which is 1.
💡 This final step concludes the algorithm by outputting the minimal achievable difference.
Line:return total - 2 * w
💡 The algorithm successfully finds the minimal last stone weight after optimal smashing.
def lastStoneWeightII(stones):
total = sum(stones) # STEP 1
half = total // 2 # STEP 1
dp = [False] * (half + 1) # STEP 2
dp[0] = True # STEP 2
for i, weight in enumerate(stones): # STEP 3-8
for w in range(half, weight - 1, -1):
dp[w] = dp[w] or dp[w - weight] # update dp
for w in range(half, -1, -1): # STEP 9
if dp[w]:
return total - 2 * w # STEP 10
if __name__ == '__main__':
stones = [2,7,4,1,8,1]
print(lastStoneWeightII(stones))
📊
Last Stone Weight II - Watch the Algorithm Execute, Step by Step
Watching the DP array update step-by-step reveals how the problem reduces to a subset sum variant and how the algorithm efficiently finds the closest sum to half the total.
Step 1/10
·Active fill★Answer cell
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
?
?
?
?
?
?
?
?
?
?
?
half
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
False
False
False
False
False
False
False
False
False
False
False
dp[0]=True
Item 0 - wt:2 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
False
True
False
False
False
False
False
False
False
False
False
dp[2] updated
Item 1 - wt:7 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
False
True
False
False
False
False
True
False
True
False
False
dp[7] updated
Item 2 - wt:4 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
False
True
False
True
False
True
True
False
True
False
True
dp[4] updated
Item 3 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
True
False
True
True
True
True
True
True
True
True
dp[1] updated
Item 4 - wt:8 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
True
False
True
True
True
True
True
True
True
True
dp[8] updated
Item 5 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
True
True
True
True
True
True
True
True
True
True
dp[3] updated
Item 5 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
True
True
True
True
True
True
True
True
True
True
answer cell
Item 5 - wt:1 val:0
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
True
True
True
True
True
True
True
True
True
True
final answer
Key Takeaways
✓ The problem reduces to finding a subset sum closest to half the total sum.
This insight is hard to see from code alone but becomes clear when watching achievable sums build up.
✓ Backward iteration in DP prevents reuse of the same stone multiple times in one iteration.
Visualizing the backward updates clarifies why the order of iteration matters.
✓ The final answer is found by scanning the DP array from half downwards to find the best achievable sum.
Seeing the final scan step highlights how the minimal difference is computed from the DP results.
Practice
(1/5)
1. Consider the following code snippet for the coin change problem. What is the value of dp[5] after the outer loop iteration i=5 completes when coins = [1, 2, 5] and amount = 5?
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount]
print(coinChange([1,2,5], 5))
Using coin 5 directly gives dp[5]=1, which is minimal.
Final Answer:
Option D -> Option D
Quick Check:
dp[5] = 1 coin (coin 5) [OK]
Hint: Direct coin equal to amount sets dp[amount] to 1 [OK]
Common Mistakes:
Off-by-one errors in indexing dp
Ignoring direct coin match
2. Consider the following Python code implementing the optimal job scheduling solution. What is the value of dp[2] after the loop iteration with i=2 when the input is startTime = [1, 2, 3], endTime = [3, 5, 10], and profit = [20, 20, 100]?
easy
A. 120
B. 20
C. 140
D. 100
Solution
Step 1: Sort jobs by end time
Jobs sorted by end time: [(1,3,20), (2,5,20), (3,10,100)]. Ends = [3,5,10]
Hint: Binary search finds last compatible job index correctly [OK]
Common Mistakes:
Off-by-one in binary search index
Using dp[i-1] incorrectly
Ignoring base case for dp[0]
3. The following code attempts to solve the integer break problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on some inputs?
def integer_break(n):
dp = [0] * n
dp[1] = 1
for i in range(2, n + 1):
max_product = 0
for j in range(1, i):
max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
dp[i] = max_product
return dp[n]
medium
A. Line 3: dp[1] = 1 base case initialization
B. Line 2: dp array size is n instead of n+1
C. Line 5: Outer loop range from 2 to n+1
D. Line 7: Using max(j, dp[j]) instead of just dp[j]
Solution
Step 1: Check dp array size
dp is initialized with size n, but indices up to n are accessed (dp[i], dp[i-j]) which requires size n+1.
Step 2: Consequences of wrong size
Accessing dp[n] or dp[i-j] when i=n causes index out of range or incorrect results.
Final Answer:
Option B -> Option B
Quick Check:
dp array must be size n+1 to safely index up to n [OK]
Hint: Check array size matches max index accessed [OK]
Common Mistakes:
Forgetting dp size off-by-one
Misplacing base case initialization
4. What is the time complexity of the bottom-up DP solution with binary search for the minimum cost tickets problem, given n travel days?
medium
A. O(n^2) because for each day we scan all future days
B. O(n log n) because for each day we perform 3 binary searches over the days array
C. O(n) because we only iterate once over the days array
D. O(n * 3 * n) due to nested loops over days and durations
Solution
Step 1: Identify loops and operations
Outer loop runs n times (for each day). Inner loop runs 3 times (for each ticket duration). Each inner iteration does a binary search (log n) to find next uncovered day.
Step 2: Calculate total complexity
Total time = n * 3 * log n = O(n log n). Linear scan or nested loops over days would be O(n^2), but binary search reduces it.
Final Answer:
Option B -> Option B
Quick Check:
Binary search reduces inner loop from O(n) to O(log n) [OK]
Hint: Binary search reduces complexity from quadratic to n log n [OK]
Common Mistakes:
Assuming inner loop is linear scan
Ignoring binary search effect
Confusing space with time complexity
5. Suppose the problem is modified so that you want to find the minimum number of perfect squares summing to n, but now each perfect square can only be used at most once. Which of the following changes correctly adapts the algorithm?
hard
A. Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse
B. Use a top-down memoized recursion with a visited set to avoid reusing squares
C. Use a 2D DP array where dp[i][j] represents minimum squares using first j squares to sum to i
D. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly
Solution
Step 1: Understand the constraint change
Limiting each perfect square to be used at most once converts the problem from unbounded to 0/1 knapsack variant, requiring tracking which squares are used.
Step 2: Identify correct DP adaptation
A 2D DP array dp[i][j] that tracks minimum squares to sum to i using first j squares correctly models the usage constraint. Other options either do not prevent reuse or do not track usage properly.
Step 3: Confirm why other options fail
Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse still allows reuse implicitly. Use a top-down memoized recursion with a visited set to avoid reusing squares is inefficient and complex. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly's order change alone doesn't enforce usage limits.