Practice
def knapsack_space_optimized(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
print(knapsack_space_optimized(weights, values, W))Solution
Step 1: Trace dp array updates for each item
For item 0 (weight=10, value=60), dp[w] updated for w=50 down to 10, dp[10..50]=60. For item 1 (weight=20, value=100), dp[30]=max(dp[30], dp[10]+100)=160, dp[50]=max(dp[50], dp[30]+100)=220. For item 2 (weight=30, value=120), dp[50]=max(dp[50], dp[20]+120)=max(220, 160+120)=280 but dp[20] is 60, so dp[50]=max(220, 180)=220.Step 2: Final dp[50] value
The maximum value achievable with capacity 50 is 220.Final Answer:
Option D -> Option DQuick Check:
Manual dp tracing confirms max value 220 [OK]
- Forwards iteration over w causes overcounting items.
dp[3] after the outer loop iteration i = 3 completes?
def integer_break(n):
dp = [0] * (n + 1)
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]
print(integer_break(4)) # Output not asked here
Solution
Step 1: Trace dp for i=2
dp[1] = 1 (given). For i=2, j=1: max_product = max(0, max(1,1)*max(1,1)) = 1, so dp[2] = 1.Step 2: Trace dp for i=3
j=1: max_product = max(0, max(1,1)*max(2,dp[2])) = max(0,1*2) = 2 j=2: max_product = max(2, max(2,dp[2])*max(1,dp[1])) = max(2,2*1) = 2 So dp[3] = 2.Final Answer:
Option A -> Option AQuick Check:
dp[3] = 2 matches manual calculation [OK]
- Off-by-one in loop bounds
- Confusing dp[i-j] with dp[j]
n. What is the value of dp[4] after the outer loop iteration i = 4 completes?Solution
Step 1: Trace dp[4] updates
For i=4, j iterates over 1 and 2 because 1*1=1 <=4 and 2*2=4 <=4. - For j=1: dp[4] = min(inf, 1 + dp[3]) = 1 + dp[3] - For j=2: dp[4] = min(previous, 1 + dp[0]) = min(previous, 1 + 0) = 1 Since dp[0] = 0, dp[4] becomes 1.Step 2: Confirm dp[4] final value
dp[4] = 1 means 4 can be represented as one perfect square (2*2). This matches the expected minimal count.Final Answer:
Option B -> Option BQuick Check:
dp[4] = 1 for 4 = 2^2 [OK]
- Off-by-one errors in loop
- Ignoring dp[0] base case
n coins and target amount amount?Solution
Step 1: Identify loops in code
Outer loop iterates over n coins, inner loop iterates over amount from coin to amount.Step 2: Calculate complexity
Each dp[w] update is O(1), total updates are roughly n * amount, so time complexity is O(n * amount).Final Answer:
Option D -> Option DQuick Check:
Nested loops over coins and amounts confirm O(n * amount) [OK]
- Confusing amount with n
- Forgetting recursion stack space
- Assuming quadratic in amount
Solution
Step 1: Identify loops in the algorithm
The algorithm has an outer loop over n elements and an inner loop over sums from S down to each num.Step 2: Calculate total operations
Each element causes up to S iterations, so total time is O(n * S). Recursive brute force is exponential, and linear or log factors are incorrect.Final Answer:
Option C -> Option CQuick Check:
Nested loops over n and S -> O(n * S) [OK]
- Confusing recursion stack space with time
- Assuming linear or exponential time incorrectly
