Knapsack and Climbing Stairs Interview Questions

Example problem (Climbing stairs): Ways to reach step n = ways(n-1) + ways(n-2). Base: 1 way to reach step 1, 2 ways to reach step 2. Use two variables for O(n) time, O(1) space.

Example problem (0/1 Knapsack): dp[i][w] = best value using first i items with capacity w. For each item, skip or take if it fits.

Because it is the smallest DP they can use to see if I write a recurrence, base cases, and then bottom-up without exploding recursion. Ways to climb n with 1 or 2 steps is dp[i] = dp[i-1] plus dp[i-2]. I can even keep two variables. They then add 1..k steps or min cost. If I cannot do stairs I will not do knapsack. I would not start with a recursive tree in code unless they ask me to explain it first.

Each item I either take or skip, and I cannot take it twice. dp[i][w] is best value using the first i items with capacity w. Transition: skip dp[i-1][w], or if weight fits, value plus dp[i-1][w minus weight]. I can compress to 1D if I iterate w backwards so I do not reuse the same item. Unbounded knapsack iterates w forwards. That backward-versus-forward 1D trick is what they want to hear.

If a local greedy choice can block a better global — coin change with arbitrary coins, not canonical denominations — I need DP. If I can prove a greedy choice stays optimal, I greedy. In interviews I say: overlapping subproblems plus optimal substructure, and I try a tiny counterexample to greedy first. Knapsack with values is the classic greedy-fails case. Climbing stairs is DP even though it looks like Fibonacci maths.

The i dimension only needs the previous row, so I can use one array of size capacity plus one. For 0/1 I loop capacity from high to low. That is O(W) extra space instead of O(nW) . I still take O(nW) time. I would not optimize space first if I cannot write the 2D version — correctness then compression. Interviewers like hearing the backward 1D loop because it proves I know why 0/1 differs from unbounded.