QuizzesDynamic Programming
advanced
dsa

Dynamic Programming

Memoization, tabulation, classic DP problems — Fibonacci, Coin Change, Knapsack, LCS, and LIS.

30 minutes 10 questions Pass at 70%
Time Limit
30 minutes - timer starts when you begin
Change Answers Freely
Revisit and change any answer before submitting
Full Review After Submit
Correct answers and explanations shown for every question
Auto-submit on timeout
Quiz submits automatically when time runs out

Questions in this quiz

10 questions on Dynamic Programming. Work through them here, then start the quiz to answer them and see your score.

  1. 1.What are the two key properties a problem must have to be solved with dynamic programming?

    • AMust be solvable by greedy algorithms first
    • BOptimal substructure (optimal solution uses optimal solutions to subproblems) and overlapping subproblems (same subproblems solved multiple times)
    • CMust involve sorting and searching
    • DMust have at most O(n²) subproblems
  2. 2.What is the difference between top-down (memoization) and bottom-up (tabulation) DP?

    • AThey always produce different answers
    • BTop-down iterates forward; bottom-up uses recursion
    • CMemoization always uses more memory than tabulation
    • DTop-down: recursive with a cache; bottom-up: iterative, filling a table from base cases upward
  3. 3.For coins = [1, 2, 5] and amount = 6, what does dp[6] equal (minimum number of coins)?

    int[] dp = new int[7];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int coin : coins) {
        for (int amt = coin; amt <= 6; amt++) {
            if (dp[amt - coin] != Integer.MAX_VALUE)
                dp[amt] = Math.min(dp[amt], dp[amt - coin] + 1);
        }
    }
    System.out.println(dp[6]);
    • A6
    • B2
    • C3
    • D1
  4. 4.What is the time and space complexity of 0/1 Knapsack DP?

    • AO(n) time, O(1) space
    • BO(n × W) time, O(n × W) space — or O(W) with 1D space optimization
    • CO(n log n) time, O(n) space
    • DO(2^n) — no DP possible
  5. 5.For n = 5, what does this classic DP code compute?

    int[] dp = new int[n + 1];
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    System.out.println(dp[n]);
    • A13
    • B7
    • C5
    • D8
  6. 6.What is the Longest Common Subsequence (LCS) problem and what is its DP time complexity?

    • AFind longest common contiguous substring — O(n²) DP
    • BFind all matching characters — O(n) DP
    • CFind longest common prefix — O(n) DP
    • DFind longest sequence of characters present in both strings in the same relative order (not necessarily contiguous) — O(m × n) DP
  7. 7.When should you use greedy instead of DP?

    • ADP works only when there are at most O(n) states
    • BGreedy is top-down; DP is bottom-up
    • CGreedy works when a locally optimal choice always leads to a globally optimal solution (provable by exchange argument); DP is needed when local choices do not guarantee global optimum
    • DAlways prefer greedy — it is faster
  8. 8.What is edit distance (Levenshtein distance) and which DP pattern does it use?

    • ACount partitions of a number — 1D DP
    • BShortest path in a graph — BFS
    • CMinimum operations (insert, delete, replace) to convert one string to another — 2D string DP
    • DCount vowels in a string — 1D DP
  9. 9.What is the optimal time complexity for Longest Increasing Subsequence (LIS)?

    • AO(n²)
    • BO(n)
    • CO(n log n)
    • DO(n log² n)
  10. 10.What is the "state" in a DP problem and why is choosing the right state critical?

    • AThe current array index
    • BThe current value of the running sum
    • CThe minimal set of information needed to fully characterize a subproblem — wrong state leads to incorrect recurrence or exponential state space
    • DThe recursion depth