Chapter quiz · Dynamic Programming

Test what you learned.

8 questions on Dynamic Programming. Pass 70% to clear the chapter.

← Review chapter lessons

Quiz

Dynamic Programming — Chapter Quiz

Eight questions on overlapping subproblems, optimal substructure, top-down vs bottom-up, knapsack, LCS, LIS, and edit distance.

0/ 9
  1. Question 1
    1

    Which two properties must a problem have for dynamic programming to apply?

  2. Question 2
    2

    What is the key difference between top-down (memoization) and bottom-up (tabulation) DP?

  3. Question 3
    3

    In the 0/1 knapsack problem with n items and capacity W, the DP table has dimensions:

  4. Question 4
    4

    The LCS (Longest Common Subsequence) recurrence for strings X and Y at position (i, j) is:

  5. Question 5
    5

    The naive O(n²) LIS (Longest Increasing Subsequence) algorithm can be improved to O(n log n) by:

  6. Question 6
    6

    Edit distance (Levenshtein distance) can be computed in O(m·n) time and O(min(m,n)) space.

  7. Question 7
    7

    In a Fibonacci DP solution, bottom-up tabulation can be further optimised to use only O(___) space by keeping just the last two values.

  8. Question 8
    8

    Which of the following problems are correctly solved by dynamic programming? (Select all that apply)

    Select all that apply.

Pick an answer — instant feedback as you go.