Course: EECS 376, Foundations of Computer Science | University of Michigan, Winter 2026 Source: Discussion Worksheet – Algorithms 2
Tags: dynamic programming, DP, optimal substructure, overlapping subproblems, recurrence, memoisation, bottom-up, tabulation, EECS 376, UMich
Difficulty: Intermediate | Prerequisites: Divide-and-conquer basics, recursion, Big-O notation
Dynamic programming (DP) is one of the most tested algorithm-design paradigms in EECS 376 and in technical interviews alike. It builds on divide-and-conquer by adding a memory layer: instead of re-solving the same subproblem over and over, you store each answer once and look it up when needed. This worksheet introduces the core theory (optimal substructure, overlapping subproblems) and walks through four concrete problems, from counting stair-climbing paths to tiling and arithmetic subsequences. If you are comfortable writing a recursive function and analysing its runtime, you are ready for this material.
Dynamic programming speeds up recursive solutions by caching results to overlapping subproblems. You design a recurrence that breaks a problem into smaller pieces, then fill a table bottom-up so every subproblem is solved exactly once. The pattern applies whenever the problem has optimal substructure and overlapping subinputs.
Dynamic programming (DP)
An algorithm-design paradigm that solves a problem by breaking it into overlapping subproblems and storing each subproblem's result so it is computed only once. In simple terms, this means: solve smaller pieces first, remember the answers, and combine them.
Optimal substructure (principle of optimality)
A problem has optimal substructure when some optimal solution to the full instance can be built from optimal solutions to smaller subinstances. Think of it as: the best overall answer is stitched together from the best answers to its parts.
Overlapping subproblems / overlapping subinputs
The property that the same smaller instances appear many times during a recursive decomposition of the original problem. In simple terms, this means: if you drew the recursion tree, you would see the same call showing up again and again.
Recurrence relation
A mathematical expression that defines the value of a function in terms of its value on smaller inputs, together with one or more base cases. Think of it as: the rule that tells you how to compute the next answer from answers you already have.
Base case
The smallest input(s) for which the answer is known directly, without further recursion. In simple terms, this means: the starting point that stops the recursion from going on forever.
Bottom-up table (tabulation)
An iterative approach that fills in a table starting from the base cases and working towards the original input, so that every needed value is ready before it is used. Think of it as: building the answer from the ground up, row by row, instead of diving in from the top.
Memoisation (top-down DP)
A recursive approach that stores each computed result in a cache and returns the cached value on repeated calls. In simple terms, this means: run the recursion as normal but keep a dictionary of what you have already solved.
Backtracking / backpointers
A technique for recovering the actual solution (not just its value) by recording, at each step, which choice led to the optimal value, then tracing those choices from the final answer back to the base case. Think of it as: leaving breadcrumbs on the way down, then following them back to reconstruct the path.
This five-step recipe appears in the worksheet and is the standard approach EECS 376 expects you to follow on exams.
Focus on the value version. Temporarily ignore finding the actual solution. Instead, ask: what is the value of an optimal solution (minimum cost, maximum count, etc.)? If the problem already asks for a count or a yes/no, this step is free.
Write the recurrence (with base cases). Figure out how the answer for a larger input relates to answers for smaller inputs. This is the creative step, and most exam questions test exactly this skill.
Implement a bottom-up table. Translate the recurrence into pseudocode that fills a table iteratively. Three guiding questions:
What are all the possible subinputs? That determines the table's dimensions.
Which cells must be filled before a given cell can be computed? That determines the fill order.
Which cell holds the final answer?
Add backtracking (if needed). If the problem asks for the solution itself (not just its value), record which choice was made at each cell and trace back from the answer cell to the base case.
Analyse the runtime. Count the number of table entries multiplied by the work per entry. This is usually straightforward once the table structure is clear.
Problem statement. There are n steps. A person at the bottom can climb 1, 2, or 3 steps at a time. CLIMB-STAIRS(n) returns the number of distinct ways to reach the top.
Building the recurrence. Consider the very first move. The person either takes 1 step (leaving n - 1 to go), 2 steps (leaving n - 2), or 3 steps (leaving n - 3). Each choice leads to an independent sub-problem of the same type. Because every way to finish from the remaining steps is a valid continuation, we add the counts:
CLIMB-STAIRS(n) = CLIMB-STAIRS(n - 1) + CLIMB-STAIRS(n - 2) + CLIMB-STAIRS(n - 3)
Base cases:
CLIMB-STAIRS(0) = 1 (one way to "climb" zero steps: do nothing)
CLIMB-STAIRS(1) = 1
CLIMB-STAIRS(2) = 2
Negative values of n return 0 by convention.
Worked example (n = 4):
CLIMB-STAIRS(4) = CLIMB-STAIRS(3) + CLIMB-STAIRS(2) + CLIMB-STAIRS(1) = 4 + 2 + 1 = 7
Bottom-up pseudocode:
CLIMB-STAIRS-DP(n):
T[0] = 1, T[1] = 1, T[2] = 2
for i = 3 to n:
T[i] = T[i-1] + T[i-2] + T[i-3]
return T[n]Runtime: O(n) time, O(n) space (reducible to O(1) space since only three previous values are needed).
Why this is DP. Overlapping subproblems: a naive recursion recomputes CLIMB-STAIRS(2) many times for large n. Optimal substructure: the total count for n is the sum of the counts for the three possible first moves.
Problem statement. Given an array M[1, ..., n] of meal sizes (number of McNuggets per meal) and a target t, determine whether it is possible to purchase exactly t McNuggets. Meals can be reused (you may buy the same meal more than once).
Example: M = [4, 6, 10, 20], t = 22. Yes, because M[2] + M[2] + M[4] = 6 + 6 + 10 = 22. Example: M = [4, 6, 10, 20], t = 13. No combination sums to 13.
Defining the subproblem. Let POSSIBLE(j) be True if exactly j McNuggets can be purchased, and False otherwise.
Recurrence:
POSSIBLE(j) = OR over all i in {1, ..., n} of POSSIBLE(j - M[i])
In words: j McNuggets can be purchased if and only if, for at least one meal size M[i], it is possible to purchase j - M[i] McNuggets.
Base cases:
POSSIBLE(0) = True (buying nothing gives exactly 0)
POSSIBLE(j) = False for all j < 0
Why it is correct. Any valid purchase of exactly j McNuggets must include at least one meal. Removing that meal leaves j - M[i] McNuggets, which must itself be achievable. The OR across all meal options captures every possible "last meal chosen."
Bottom-up pseudocode:
MCNUGGETS-DP(M, n, t):
T[0] = True
for j = 1 to t:
T[j] = False
for i = 1 to n:
if j >= M[i] and T[j - M[i]] == True:
T[j] = True
break
return T[t]Runtime: O(t * n). The outer loop runs t times, and the inner loop runs at most n times per iteration.
Real-world connection. This is a variant of the unbounded subset-sum (or coin-change feasibility) problem. The same pattern appears in making change with a set of coin denominations.
Students often think every recursive problem is a DP problem. It is not. DP requires both optimal substructure and overlapping subproblems. A problem with non-overlapping subproblems (such as merge sort) is plain divide-and-conquer.
Students sometimes confuse memoisation (top-down) with tabulation (bottom-up). Both avoid redundant work, but tabulation fills the table iteratively and avoids recursion-stack overhead, which is what EECS 376 typically asks for.
A common error on the McNuggets-style problems is forgetting to handle negative indices. If j - M[i] < 0, that subproblem does not exist; your code must guard against it.
Students frequently define incorrect base cases. For counting problems, the base case for an "empty" input is often 1 (there is one way to do nothing), not 0. Getting this wrong propagates errors through the entire table.
The five-step DP cookbook (value version, recurrence, table, backtracking, runtime) is the expected structure for any DP answer on a 376 exam. Skipping a step, especially the base cases or the runtime analysis, loses marks.
Exam questions often give you a new problem and ask only for the recurrence plus base cases. Practise writing these quickly and clearly.
Runtime analysis for DP is almost always: (number of table cells) x (work per cell). State this formula explicitly in your answer.
Backtracking questions appear less frequently but are high-value when they do. The key is recording which branch the recurrence chose at each cell.
True or False: Dynamic programming is applicable whenever a problem can be divided into subproblems, even if those subproblems do not overlap. (False: overlapping subproblems are required.)
True or False: CLIMB-STAIRS(0) = 0. (False: CLIMB-STAIRS(0) = 1, because there is exactly one way to climb zero steps.)
Fill in the blank: The runtime of the McNuggets DP solution is O(____). (t * n)
True or False: In bottom-up DP, you must always fill the table from left to right. (False: the fill order depends on the recurrence's dependencies. Left-to-right is common but not universal.)
Fill in the blank: CLIMB-STAIRS(5) = ____. (13)
Q: What two properties must a problem have for dynamic programming to apply?
A: Optimal substructure (an optimal solution is built from optimal solutions to subproblems) and overlapping subproblems (the same subproblems recur during recursion).
Q: Write the recurrence and base cases for CLIMB-STAIRS(n) where steps of size 1, 2, or 3 are allowed.
A: CLIMB-STAIRS(n) = CLIMB-STAIRS(n-1) + CLIMB-STAIRS(n-2) + CLIMB-STAIRS(n-3), with CLIMB-STAIRS(0) = 1, CLIMB-STAIRS(1) = 1, CLIMB-STAIRS(2) = 2.
Q: For the McNuggets problem with M = [4, 6, 10, 20] and t = 22, describe how POSSIBLE(22) is evaluated.
A: POSSIBLE(22) checks POSSIBLE(22 - 4) = POSSIBLE(18), POSSIBLE(22 - 6) = POSSIBLE(16), POSSIBLE(22 - 10) = POSSIBLE(12), and POSSIBLE(22 - 20) = POSSIBLE(2). If any of those is True, then POSSIBLE(22) = True. Since POSSIBLE(12) = True (via 6 + 6), the chain confirms POSSIBLE(22) = True.
Q: Why is a naive recursive solution to CLIMB-STAIRS exponential in runtime?
A: Without memoisation, the recursion tree branches three ways at each level, and the same subproblems are recomputed many times. The number of recursive calls grows as O(3^n), which is exponential.
Q: In the DP cookbook, what is the purpose of step 4 (backtracking)?
A: Step 4 recovers the actual solution, not just its optimal value. By recording which choice produced each cell's value, you trace from the final answer back through the table to reconstruct the sequence of decisions.
Dynamic programming extends the divide-and-conquer framework covered earlier in EECS 376. Where divide-and-conquer problems (merge sort, binary search) have non-overlapping subproblems, DP problems reuse the same sub-solutions many times.
The McNuggets problem connects directly to the coin-change problem studied in most algorithms courses. The same recurrence pattern appears in knapsack variants, which EECS 376 covers later.
CLIMB-STAIRS is structurally identical to computing generalised Fibonacci numbers. If you are comfortable with Fibonacci, the extension to three-step climbing (a "tribonacci" sequence) is natural.
Related Terms / Search Tags
dynamic programming, DP, optimal substructure, overlapping subproblems, recurrence relation, memoisation, memoization, tabulation, bottom-up DP, top-down DP, value version, backtracking, backpointers, stair climbing problem, McNuggets problem, coin change, subset sum, unbounded knapsack, Fibonacci, tribonacci, EECS 376, UMich, Foundations of Computer Science