Course: EECS 376, Foundations of Computer Science | University of Michigan, Winter 2026 Source: Discussion Worksheet – Algorithms 2
Tags: dynamic programming, tilings, longest arithmetic subsequence, binary strings, no consecutive 1s, recurrence, bottom-up DP, EECS 376, UMich
Difficulty: Intermediate | Prerequisites: Part 1 of these notes (DP fundamentals, the DP cookbook)
This second set of notes covers the three remaining problems from the EECS 376 Discussion Worksheet on dynamic programming. Each problem reinforces the same five-step DP framework introduced in Part 1 but with different flavours: Tilings is a counting problem with variable block lengths, Longest Arithmetic Subsequence introduces a hash-map-based DP table, and Binary Strings Without Consecutive 1s connects DP to the Fibonacci sequence. Together they build fluency in recognising DP patterns and writing recurrences under exam conditions.
Three more DP problems, each solved by defining a subproblem, writing a recurrence with base cases, and implementing a bottom-up table. Tilings generalises stair-climbing to arbitrary block lengths. Longest Arithmetic Subsequence uses a per-element DP value keyed on the previous element. Binary Strings shows that the Fibonacci recurrence emerges naturally from a constraint on consecutive characters.
Problem statement. Tile a path of length n using k types of blocks with distinct lengths l_1, l_2, ..., l_k. Each block type has an infinite supply. TILINGS(i) returns the total number of ways to tile a path of length i. Target runtime: O(nk).
Consider the first block placed. If it has length l_j, the remaining path has length i - l_j. Summing over all valid block types gives:
TILINGS(i) = sum over all j in {1, ..., k} where l_j <= i of TILINGS(i - l_j)
Base case: TILINGS(0) = 1 (there is exactly one way to tile an empty path: use no blocks).
For any i < 0, TILINGS(i) = 0 (no block can fit a negative-length path).
Why it is correct. Every tiling of a path of length i must begin with some block. That first block's length l_j partitions the set of all tilings into k disjoint groups (one per block type that fits). The counts of these groups are independent sub-problems of the same form, so we add them.
TILINGS-DP(n, k, l[1..k]):
T[0] = 1
for i = 1 to n:
T[i] = 0
for j = 1 to k:
if l[j] <= i:
T[i] = T[i] + T[i - l[j]]
return T[n]Runtime analysis. The outer loop runs n times. The inner loop runs k times per iteration. Each inner iteration does O(1) work (one addition, one comparison). Total: O(nk).
Space: O(n) for the table.
Connection to Climb Stairs. Climb Stairs is the special case where k = 3 and the block lengths are l_1 = 1, l_2 = 2, l_3 = 3. If you solved Climb Stairs, you have already solved a Tilings instance.
Problem statement. Given an array of integers A[1, ..., n] and a fixed difference d, find the length of the longest subsequence S of A such that S[i + 1] - S[i] = d for every consecutive pair.
Defining the subproblem. Let LAS(i) be the length of the longest arithmetic subsequence with difference d that ends at index i.
Recurrence:
LAS(i) = 1 + max over all j < i where A[i] - A[j] = d of LAS(j)
If no such j exists, LAS(i) = 1 (the subsequence containing only A[i]).
Base case: LAS(i) = 1 for every i (every single element is a valid arithmetic subsequence of length 1).
Final answer: max over all i in {1, ..., n} of LAS(i).
Efficient implementation with a hash map. A naive implementation scans all j < i for each i, giving O(n^2). A faster approach uses a hash map H where H[v] stores the length of the longest arithmetic subsequence ending with value v.
LAS-DP(A, n, d):
H = empty hash map
best = 1
for i = 1 to n:
prev = A[i] - d
if prev in H:
H[A[i]] = H[prev] + 1
else:
H[A[i]] = 1
best = max(best, H[A[i]])
return bestRuntime: O(n) with the hash map (assuming O(1) expected-time hash operations). Without the hash map, the straightforward two-loop approach is O(n^2).
Why it works. When processing A[i], the value A[i] - d is the element that must immediately precede A[i] in any arithmetic subsequence with difference d. If that value has already been seen, we extend its subsequence by one. The hash map stores only the best result per value, which is sufficient because two subsequences ending at the same value are interchangeable for future extensions.
Real-world connection. Longest arithmetic subsequence problems appear in pattern detection, time-series analysis, and number theory. The hash-map technique is a useful general pattern for DP problems where the "previous state" is determined by a computed value rather than an adjacent index.
Problem statement. Let C(l) be the number of binary strings of length l that contain no two consecutive 1s. For example, C(3) = 5 (the valid strings are 000, 001, 010, 100, 101).
Build the table step by step:
C(0) = 1 (the empty string)
C(1) = 2 (strings: 0, 1)
C(2) = 3 (strings: 00, 01, 10)
C(3) = 5
C(4) = C(3) + C(2) = 5 + 3 = 8
C(5) = C(4) + C(3) = 8 + 5 = 13
A brute-force approach enumerates all 2^l binary strings and checks each for consecutive 1s. For large l, this is O(l * 2^l): exponential growth makes it infeasible even for moderate lengths (e.g., l = 50 produces over 10^15 strings).
Claim: C(l) = C(l - 1) + C(l - 2) for l >= 2.
Proof. Partition all valid strings of length l by their first character:
Strings starting with 0: the remaining l - 1 characters can be any valid string of length l - 1, giving C(l - 1) valid strings.
Strings starting with 1: to avoid consecutive 1s, the second character must be 0. The remaining l - 2 characters can be any valid string of length l - 2, giving C(l - 2) valid strings.
These two groups are disjoint and exhaustive, so C(l) = C(l - 1) + C(l - 2).
Base cases: C(0) = 1, C(1) = 2.
This is the Fibonacci recurrence (shifted by initial values). A naive recursive implementation has exponential runtime because C(l - 1) and C(l - 2) share overlapping sub-calls.
C-DP(l):
T[0] = 1, T[1] = 2
for i = 2 to l:
T[i] = T[i-1] + T[i-2]
return T[l]Runtime: O(l) time, O(l) space (reducible to O(1) since only two previous values are needed).
This is a textbook example of converting an exponential-time recursion into a linear-time DP solution by recognising overlapping subproblems.
Students often confuse Tilings with permutations. The tiling problem counts ordered sequences of blocks (the order in which blocks are placed matters), so it is a sum over choices for the first block, not a combination formula.
For Longest Arithmetic Subsequence, a common mistake is treating it as a contiguous subarray problem. It is a subsequence problem: elements need not be adjacent in the original array.
When proving C(l) = C(l - 1) + C(l - 2), students sometimes partition by the last character instead of the first. Both work, but the logic for the "1" case differs: if the last character is 1, the second-to-last must be 0, leaving C(l - 2).
Students occasionally set C(0) = 0 instead of C(0) = 1. The empty string trivially satisfies "no consecutive 1s," so it counts as one valid string.
Tilings is the most general version of the stair-climbing pattern. If you can write this recurrence fluently, you can handle any "how many ways to cover/fill/partition" question.
Longest Arithmetic Subsequence tests whether you can pick the right DP state. Expect exam questions where the subproblem definition is the hard part, not the recurrence itself.
Binary Strings is a classic "prove the recurrence" question. Be prepared to write a short proof by case analysis (partition by first or last character) and state the base cases clearly.
Runtime analysis for all three problems follows the standard pattern: count cells, multiply by work per cell. Write this out explicitly on exams, even when it seems obvious.
Fill in the blank: TILINGS(0) = ____. (1)
True or False: The Longest Arithmetic Subsequence problem requires elements to be contiguous in the original array. (False: it is a subsequence, not a subarray.)
Fill in the blank: C(6) = ____. (C(5) + C(4) = 13 + 8 = 21)
True or False: The hash-map approach for LAS runs in O(n^2) time. (False: it runs in O(n) expected time with O(1) hash operations.)
Fill in the blank: The brute-force runtime for binary strings of length l is O(____). (l * 2^l)
Q: Write the recurrence and base case for TILINGS(i) with block lengths l_1, ..., l_k.
A: TILINGS(i) = sum of TILINGS(i - l_j) for all j where l_j <= i. Base case: TILINGS(0) = 1.
Q: For the Longest Arithmetic Subsequence with A = [3, 5, 7, 9, 4, 6, 8] and d = 2, what is the answer?
A: The longest arithmetic subsequence with difference 2 is [3, 5, 7, 9], which has length 4.
Q: Prove that C(l) = C(l - 1) + C(l - 2) for l >= 2.
A: Partition valid strings of length l by the first character. Starting with 0: the remaining l - 1 bits form any valid string, giving C(l - 1). Starting with 1: the next bit must be 0 (to avoid "11"), and the remaining l - 2 bits form any valid string, giving C(l - 2). The groups are disjoint and cover all valid strings.
Q: What is the runtime of the bottom-up Tilings algorithm?
A: O(nk), where n is the path length and k is the number of block types. The outer loop runs n times and the inner loop runs k times.
Q: Why does the hash-map LAS approach store only one value per key, rather than a list of all subsequences ending at that value?
A: Because we only need the length of the longest such subsequence. Any shorter subsequence ending at the same value would never produce a longer extension than the longest one, so storing just the maximum is sufficient.
Tilings generalises the Climb Stairs problem from Part 1. The same recurrence template (sum over possible first choices) appears in coin-change counting, rod-cutting, and other combinatorial DP problems throughout EECS 376 and beyond.
The Longest Arithmetic Subsequence problem is a cousin of the Longest Increasing Subsequence (LIS), one of the most classic DP problems. The hash-map optimisation here mirrors techniques used in LIS variants and in problems involving subsequences with specific gap constraints.
Binary Strings Without Consecutive 1s produces the Fibonacci sequence (shifted by initial values). Fibonacci-type recurrences appear across combinatorics, number theory, and even in the analysis of algorithms such as Euclid's GCD.
Related Terms / Search Tags
dynamic programming, tilings, path tiling, block tiling, longest arithmetic subsequence, LAS, arithmetic progression, binary strings, no consecutive ones, Fibonacci, overlapping subproblems, recurrence relation, bottom-up DP, hash map DP, coin change, rod cutting, longest increasing subsequence, LIS, EECS 376, UMich, Foundations of Computer Science, discussion worksheet, algorithms