Lab: DP problems
Three guided bottom-up DP exercises — word break, house robber, and longest increasing subsequence.
- Solve word break bottom-up with a boolean DP array
- Solve house robber with a rolling two-variable window
- Solve longest increasing subsequence in O(n²) and understand the O(n log n) improvement
Three problems that appear constantly in interviews and real systems. Each one has a clean bottom-up formulation once you name the sub-problem correctly. Work through the "think first" prompt before reading the scaffold.
Problem 1: word break
Problem. Given a string s and a list of dictionary words, return True
if s can be segmented into a sequence of dictionary words.
word_break("leetcode", ["leet", "code"]) → True.
Think first. What does dp[i] represent? One natural choice: dp[i] is
True if s[:i] can be segmented. If dp[j] is True for some j < i and
s[j:i] is in the dictionary, then dp[i] is True. The base case is
dp[0] = True (empty prefix needs no words).
Implement word_break(s, word_dict) returning True if s can be segmented into words from word_dict. Use bottom-up DP: dp[i] = True if s[:i] can be broken.
word_break("leetcode", ["leet","code"]) → Trueword_break("catsandog", ["cats","dog","sand","and","cat"]) → FalseTop-down alternative. The same idea with memoisation: a recursive function
can_break(i) checks all splits s[:j]/s[j:i]. The recursion can hit the
same index many times, so caching (@functools.lru_cache) brings it to O(n²)
as well. Bottom-up avoids Python's recursion overhead.
Problem 2: house robber
Problem. Given an array of non-negative integers representing the money in
each house, return the maximum amount you can rob without robbing two adjacent
houses. house_robber([2, 7, 9, 3, 1]) → 12.
Think first. At each house you have two choices: rob it (adding its value to the best result from two houses ago) or skip it (keeping the best result from the previous house). You only ever need the previous two values, so this is O(1) space.
Implement house_robber(nums) returning the maximum money robbable without touching adjacent houses. Use a rolling two-variable window.
house_robber([2,7,9,3,1]) → 12house_robber([1,2,3,1]) → 4Why rolling window? The full DP array dp[i] = max(dp[i-1], dp[i-2] + nums[i])
is correct but wastes memory: each step only reads the previous two cells.
Replacing the array with two scalars cuts space from O(n) to O(1).
Problem 3: longest increasing subsequence
Problem. Given a list of integers, return the length of the longest
strictly increasing subsequence. The subsequence need not be contiguous.
lis([10, 9, 2, 5, 3, 7, 101, 18]) → 4 (one valid LIS: [2, 5, 7, 101]).
Think first. dp[i] = length of the longest increasing subsequence that
ends at index i. For every earlier index j where nums[j] < nums[i],
dp[i] can be at least dp[j] + 1. This is O(n²). There is an O(n log n)
approach using patience sorting (binary search to maintain a "tails" array),
but the O(n²) version is far easier to derive and is worth knowing cold.
Implement lis(nums) returning the length of the longest strictly increasing subsequence. O(n²) DP: dp[i] is the LIS length ending at index i.
lis([10,9,2,5,3,7,101,18]) → 4lis([7,7,7,7]) → 1The O(n log n) approach maintains a list tails where tails[i] holds the
smallest tail element of any increasing subsequence of length i+1. For each
number, binary-search for the leftmost position in tails that is greater
than or equal to it and replace that element. The length of tails at the
end is the LIS length. This uses bisect_left from Python's standard library.
Where to go next
These three problems are a sampler of the broader DP landscape. Next up is the Advanced Graphs module, where you will meet Dijkstra's algorithm and topological sort — graph algorithms that also rely on careful state tracking and greedy reasoning.