Unit 4: Basic Dynamic Programming - Practice Quiz

1 What is the main purpose of dynamic programming?

2 Which two properties are commonly associated with dynamic programming problems?

3 In the Fibonacci sequence, what is the value of when and ?

4 What recurrence relation represents the Fibonacci sequence?

5 How many ways can a board usually be tiled using dominoes?

6 For a tiling problem, what can be placed at the left end of the board?

7 If a person can climb either 1 or 2 stairs at a time, how many ways are there to climb 3 stairs?

8 What recurrence is commonly used for the climbing stairs problem when 1-step and 2-step moves are allowed?

9 What is memoization in dynamic programming?

10 What is tabulation in dynamic programming?

11 Which approach generally avoids recursive function calls?

12 In dynamic programming, what does a state usually represent?

13 What is a state transition in dynamic programming?

14 For climbing stairs, if stores the number of ways to reach stair , which transition is correct?

15 What does the optimal substructure property mean?

16 Which type of problem is most likely to have optimal substructure?

17 What are overlapping subproblems?

18 Why does dynamic programming store results of subproblems?

19 Which step should usually be performed first when solving a dynamic programming problem?

20 What is a base case in dynamic programming?

21 Which situation most strongly suggests that dynamic programming should be used?

22 A recursive algorithm makes many repeated calls with the same arguments. What change most directly converts it into a dynamic programming solution?

23 Using , , and , what is the minimum auxiliary space needed to compute only iteratively?

24 A memoized recursive implementation computes . If each state for is evaluated at most once, what is its time complexity?

25 A board is tiled using dominoes placed vertically or horizontally. Which recurrence correctly counts the tilings?

26 For the domino tiling problem with and , how many tilings exist for a board?

27 A person may climb , , or stairs at a time. If is the number of ways to reach stair , which transition is correct for ?

28 In a minimum-cost climbing problem, stepping on stair costs , and one may move one or two stairs. If is the minimum cost to reach stair , which transition is appropriate?

29 A problem has possible states, but a particular input reaches only states, where . Which approach may avoid evaluating the unreachable states?

30 Which implementation issue is generally avoided by replacing a deep top-down memoized solution with an equivalent bottom-up tabulation?

31 For the knapsack problem, which state definition contains enough information to decide whether item may be included?

32 Let be the length of the longest increasing subsequence ending at index . Which transition correctly computes ?

33 Why does the shortest-path problem exhibit optimal substructure when all considered path costs are well-defined?

34 An optimization problem lacks optimal substructure. What is the main consequence for a proposed dynamic programming recurrence?

35 In the naive recursive computation of , which observation demonstrates overlapping subproblems?

36 A divide-and-conquer algorithm splits an input into disjoint subarrays that are never processed again. Why might memoization provide little benefit?

37 After defining states and deriving a transition, what should be established before filling a bottom-up DP table?

38 A two-dimensional DP transition uses only the current row and the immediately preceding row. Which optimization is generally valid?

39 To find the minimum number of coins needed to form amount with unlimited coin reuse, which recurrence is appropriate?

40 A robot moves from the top-left to the bottom-right of a grid using only right or down moves. Some cells are blocked. If counts valid paths to cell , how should a blocked cell be handled?

41 A recurrence is defined by with . Under which condition can all states be evaluated once in a fixed order without repeated relaxation?

42 Suppose and . A fast-doubling algorithm recursively computes . Which identities correctly produce ?

43 Let be the number of tilings of a board using dominoes. Exactly one specified cell in the top row of column , where , is blocked. Which expression gives the number of valid tilings?

44 A climber may take , , or steps at a time. Landing on step is forbidden, but jumping over it is allowed. If counts sequences that land exactly on step , what is ?

45 A DP has states for and , but from the initial state only states are reachable. Each state has outgoing transitions. Ignoring recursion-stack limits, which comparison is most accurate?

46 Count length- strings over that contain neither nor as a substring. What is the smallest generally sufficient suffix-based state for a left-to-right DP?

47 In weighted interval scheduling, jobs are sorted by nondecreasing finish time. Let be the largest index whose job finishes no later than job starts, and let be the maximum weight using jobs through . Which transition is correct?

48 A proposed DP for the longest simple path uses , the longest simple path from vertex to a target, and transitions to for each neighbor . Why is this state invalid on a general cyclic graph?

49 The naive recursion for uses . For all , how many distinct valid states can be reached from ?

50 A DP transition for state reads only states connected to by incoming dependency edges. What condition is necessary and sufficient for evaluating every state exactly once using a static linear order?

51 For 0/1 knapsack, a one-dimensional table uses for each item . In which order must capacities be processed to prevent using item multiple times?

52 An implementation computes with the recurrence . Why must the pair , rather than a single residue , be used to detect that the sequence has restarted?

53 Let count tilings of a board with dominoes and L-trominoes, where rotations are allowed. Using , , and , which recurrence is valid for ?

54 A climber must reach step using jumps of size or , but two jumps of size may not be consecutive. Which state formulation gives a correct DP?

55 A top-down DP recursively follows a dependency chain of length , and every state is reachable. A bottom-up order is known, and only the previous two values are needed. Which implementation tradeoff is most decisive?

56 For edit distance with insertion, deletion, substitution, and adjacent transposition, why is the usual transition based only on , , and insufficient?

57 Let be the length of the longest increasing subsequence ending exactly at index . Which statement justifies the transition ?

58 Consider the recursion with base case . Which observation most directly supports memoization?

59 A minimum-cost DP is compressed from a full table to two rolling rows. Later, the program must output one optimal sequence of decisions. What is the central issue with the compressed representation?

60 You must choose a maximum-value subset of tasks. Each task has a start time, finish time, value, and category; chosen tasks may not overlap, and at most category changes are allowed in chronological order. Which DP state is sufficient after sorting tasks by finish time?