Skills101
← All practice quizzes

Quiz: 1D Dynamic Programming Patterns

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Four classic one-dimensional DP problems solved with the same recipe — define the state, write the recurrence, set the base case, fill the table — plus space saving and the O(n log n) LIS trick.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    In the DP recipe, what should you decide first?

  2. Question 2

    What does this print?

    def ways(n):
        a, b = 1, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b
    print(ways(6))
    
  3. Question 3

    In house robber, why is dp[i] = max(dp[i − 1], dp[i − 2] + money[i])?

  4. Question 4

    With coins {1, 3, 4} and amount 6, what does greedy (largest coin first) give, and what is optimal?

  5. Question 5

    What does this print?

    coins, amount = [1, 2, 3], 4
    ways = [1] + [0] * amount
    for c in coins:
        for x in range(c, amount + 1):
            ways[x] += ways[x - c]
    print(ways[amount])
    
🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →