Skills101
← All practice quizzes

Quiz: DP on Grids and Strings

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

Two-dimensional DP made simple. Count grid paths (with obstacles), find the minimum path sum, compute the longest common subsequence and the edit distance, and read the answer back from the table.

Log in to take the quiz

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

  1. Question 1

    In unique paths (moves only right or down), why is dp[i][j] = dp[i − 1][j] + dp[i][j − 1]?

  2. Question 2

    What does this print?

    R, C = 3, 3
    dp = [[1] * C for _ in range(R)]
    for i in range(1, R):
        for j in range(1, C):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    print(dp[2][2])
    
  3. Question 3

    In LCS, what happens when a[i − 1] equals b[j − 1]?

  4. Question 4

    What does this print?

    a, b = "abcd", "acbd"
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    print(dp[-1][-1])
    
  5. Question 5

    What is the difference between a subsequence and a substring?

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →