Mid-levelMid (3–6 yrs)CodingPythonAmazonGoogleGoldman Sachs
0/1 Knapsack intuition
Explain the 0/1 knapsack DP recurrence and optimize space.
Answers use simple, clear English.
Time: O(nW)Space: O(W)
Quick interview answer
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight fits. Space-optimize to 1D array updated backward so each item is used at most once.
Detailed answer
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight fits. Space-optimize to 1D array updated backward so each item is used at most once.
midsenior#dp#knapsack