Skip to main content

DP Foundations and State Design Lab

Retrieval Prompts​

  1. State the two structural conditions that license DP on a problem.
  2. Describe the cut-and-paste argument in one sentence.
  3. State the difference between memoization and tabulation, and one scenario where each is preferable.
  4. Describe reconstruction of a DP solution in terms of parent pointers or choice arrays.
  5. Name one problem whose naive recursion is exponential and whose memoized version is polynomial.

Compare and Distinguish​

Separate these pairs clearly:

  • optimal substructure versus overlapping subproblems (both must hold for DP)
  • memoization versus tabulation (top-down vs bottom-up; sparse vs dense)
  • computing the optimal value versus reconstructing the optimal object
  • "a problem has subproblems" versus "a problem has overlapping subproblems"

Common Mistake Check​

For each statement, identify the error:

  1. "Merge sort is a DP because it is recursive."
  2. "I memoized my recursion and it got much faster, so DP applies to this problem."
  3. "The DP table stores the answer value, so reconstruction is trivial."
  4. "Tabulation is always faster than memoization."
  5. "My greedy got the right answer on the examples, so the problem admits greedy."

Mini Application​

For each problem, do all four tasks:

  1. Define the state and say what the indices mean in a complete sentence.
  2. Write the recurrence and its base cases.
  3. Decide whether memoization or tabulation is preferable, and explain why.
  4. Describe how you would reconstruct the optimal object, not just its value.

Problems:

  1. Minimum coins to make amount A using coins c[1..k] (each unlimited).
  2. Number of distinct ways to climb n stairs taking 1, 2, or 3 steps.
  3. Maximum sum of non-adjacent elements in an array a[1..n].
  4. Given a rod of length n with price table p[1..n], find the maximum revenue and the list of piece lengths.

Evidence Check​

This page is complete only if, for each of the four problems above, you can state the recurrence from memory, justify the DP paradigm choice, and describe reconstruction without looking at any reference.

Integrated Memoization and Tabulation Drill​

For each problem, solve it twice: once top-down with memoization and once bottom-up with tabulation.

  1. Fibonacci with call-count instrumentation.
  2. Minimum coins for an amount.
  3. Number of grid paths from top-left to bottom-right with blocked cells.
  4. Longest common subsequence length for two short strings.

For each solution:

  • write the state as a sentence before coding
  • list base cases separately from transitions
  • record the table shape or memo keys
  • write whether reconstruction is possible and what extra parent information would be needed

Classification prompt: for each problem, write why a greedy rule is tempting and either prove it works or give a counterexample.