Dynamic Programming Quiz — Quiz

Question 1

Dynamic programming helps most when a recursive solution has…

Overlapping subproblems (the same subproblem solved many times)No base caseOnly one recursive callSorted input

Question 2

In how many distinct ways can you climb 5 stairs taking 1 or 2 steps at a time?

Question 3

What is the maximum you can rob from houses [2, 7, 9, 3, 1] without robbing adjacent houses?

Question 4

Coins [1, 3, 4], amount 6. What is the minimum number of coins?

Question 5

What is the length of the longest common subsequence of "abcde" and "ace"?

Question 6Select all that apply

Which statements about memoization vs tabulation are true? (select all that apply)

Memoization is top-down recursion with a cacheTabulation fills a table bottom-up with loopsBoth usually have the same time complexityTabulation always uses less memory

Question 7

In 0/1 knapsack (each item at most once) with a 1D dp array, the inner loop over capacity should go…

Upwards (small to large)Downwards (large to small)In random orderIt doesn't matter

Question 8

How is the time complexity of a DP solution usually estimated?

Number of states × work per stateAlways O(n²)Number of base casesDepth of recursion only