Grid and Position DP
What is this?
Each of these indexes by a position and needs exactly one extra coordinate to close the recurrence. A grid cell needs nothing more, because the strictly-increasing rule makes the graph acyclic on its own. Typing needs to know where the other finger is. Shelving needs to know where the current row started. Scheduling needs to know the last job that finished in time, which is a binary search rather than a loop.
Fun fact: Minimum Distance to Type a Word Using Two Fingers looks like it needs a state of
(index, finger1, finger2): 27 × 27 finger placements at every index (26 letters plus a "not placed yet" slot). It does not. After typingword[i−1], one of the fingers is necessarily onword[i−1], which is already known from the index. So only the other finger's position needs storing, and the state collapses to(index, other). Recognising that part of a state is implied by the rest is one of the most reliable ways to turn a DP that will not fit into one that does.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Rule of thumb: write down the smallest thing you must remember besides the position. Anything the index already implies is not state, and removing it is usually the difference between passing and timing out.
1. When the rule makes it acyclic
@lru_cache(None)
def go(r, c):
best = 1
for nr, nc in neighbours(r, c):
if mat[nr][nc] > mat[r][c]: # strictly greater → no cycles possible
best = max(best, 1 + go(nr, nc))
return best
return max(go(r, c) for r in range(m) for c in range(n))
No visited set is needed, and that is the point worth saying aloud: because every step strictly increases, a path can never return to a cell it has left. The memo makes each cell computed once, giving O(mn).
The catch is recursion depth. On a 200 by 200 grid that climbs in a snake, the DFS goes about 40,000 frames deep, and Python's default limit is 1000. The lesson's third approach avoids recursion: count each cell's larger neighbours (its out-degree), peel off the cells with out-degree 0 as layer 1, then repeat. The number of layers is the answer, still O(mn).
2. When part of the state is implied
@lru_cache(None)
def go(i, other): # other = the finger NOT on word[i-1]
if i == len(word): return 0
prev = word[i-1] if i else None
return min(dist(prev, word[i]) + go(i+1, other), # same finger continues
dist(other, word[i]) + go(i+1, prev)) # the other finger moves
Two choices per character, and None (no finger placed yet) costs zero to move from, which handles the first two characters without a special case. Distance is Manhattan on the 6-wide keyboard grid: divmod(ord(ch) - ord('A'), 6). The word has 2 to 300 letters, and since each row of the table depends only on the next, the bottom-up version needs just O(27) space.
3. When the choice is where the group begins
for i in range(1, n + 1):
w = h = 0
for j in range(i, 0, -1): # books j..i share the last shelf
w += books[j-1][0]
if w > shelf_width: break # cannot widen further
h = max(h, books[j-1][1])
dp[i] = min(dp[i], dp[j-1] + h)
Walking backwards from i is what lets the width accumulate incrementally and the break fire as soon as the shelf is full. Books must stay in order, which is why "which books share the last shelf" is always a contiguous suffix, and that is the fact that makes the whole DP work.
Greedy (fill each shelf as full as possible) loses. With books [[1,1],[1,2],[2,2]] and shelfWidth = 3, greedy puts books 1 and 2 together and book 3 alone for a height of 4. Book 1 alone and books 2 and 3 together gives 3.
4. When the transition is a binary search
jobs = sorted(zip(end, start, profit)) # sorted by end time
ends = [j[0] for j in jobs]
dp = [0] * (n + 1) # dp[i] = best using the first i jobs
for i in range(1, n + 1):
e, s, p = jobs[i - 1]
k = bisect_right(ends, s, 0, i - 1) # jobs finishing at or before s
dp[i] = max(dp[i - 1], p + dp[k]) # skip it, or take it
return dp[n]
Sorting by end time is what makes ends increasing and therefore searchable, and it makes the compatible jobs a prefix of the sorted list. dp[i] never decreases, so dp[n] is the answer. This is the weighted version of interval scheduling. It is not the unweighted LeetCode 1353 problem, which is a different task.
5. A 30-second worked example (two fingers)
word = "CAKE" on a 6-wide keyboard: A is (0,0), C is (0,2), E is (0,4), K is (1,4).
Distances: C→A = 2, C→K = 3, A→K = 5, K→E = 1.
The greedy's free move at step 2 is what costs it. Placing the second finger on A looks like a saving of 2 and leaves both fingers stranded on the left of the keyboard, while K and E are both on the right. Paying the 2 to keep a finger free is worth it, and no rule about the current character can see that, which is exactly why the problem is a DP.
6. Where you'll actually meet this
- Text layout. Filling shelves is the same recurrence as breaking a paragraph into lines under a width limit, where each line costs its tallest item.
- Revenue management. Weighted job scheduling underlies ad slots, meeting rooms and rental bookings.
- Terrain. Longest increasing path is the longest uphill walk over a height map.
- Keyboard layout. Finger travel distance is a common way to compare layouts.
- Resource planning. "Group consecutive items under a capacity limit" appears in shipping, batching and pagination.
7. Problems in this chapter
Longest Increasing Path in a Matrix
Longest strictly increasing path. Memoized DFS: the increase rule makes cycles impossible, so no visited set is needed. A snake grid recurses about 40,000 deep, so know the iterative peeling version too.
Pattern: memoized DFS on an implicit DAG. Target: O(mn) time and space.
Minimum Distance to Type a Word Using Two Fingers
Least total finger travel (Manhattan distance, word length 2 to 300). State is (index, other finger) because one finger is always on the previous character.
Pattern: DP with an implied state component. Target: O(n · 27) time, O(27) space bottom-up.
Filling Bookcase Shelves
Least total height with books kept in order. For each prefix, try every contiguous suffix as the last shelf. Greedy filling is wrong.
Pattern: prefix DP over contiguous groups. Target: O(n²) time, O(n) space.
Maximum Profit in Job Scheduling
Maximum profit from non-overlapping jobs. Sort by end time and binary-search the last compatible job.
Pattern: DP + binary search. Target: O(n log n) time, O(n) space.
8. Common pitfalls
- Adding a visited set to the increasing path. Strict increase already forbids revisiting, and the set breaks the memo.
- Storing both finger positions. One of them is implied by the index, so the state is 27 values per index, not 27 × 27.
- Walking shelves forward. Backwards accumulation is what lets the width check break early.
- Forgetting books must stay in order, which is what makes the last shelf a contiguous suffix.
- Sorting jobs by start time. End time is what makes the binary search possible.
- Using
bisect_lefton the ends array. A job that ends exactly when the next begins is compatible, so you needbisect_right(the count of ends at or below the start). - Greedy shelf filling. Packing each shelf as full as possible can lose, as the
[[1,1],[1,2],[2,2]]example shows. - Recursive longest path on a big grid in Python. A snake overflows the default recursion limit.
- Memoising on mutable state. Keys must be the position and the small extra coordinate, nothing else.
9. Key takeaways
- State = position + the smallest thing you must remember. Anything implied is not state.
- A strict-increase rule gives you a DAG for free: no visited set, no cycle handling.
- Contiguity is a gift. "Books stay in order" is what makes the shelf a suffix.
- Sort to make a transition searchable. By end time, then bisect.
- Keeping a DP array monotonic means the answer is always its last element.
Noneas an initial position removes the special case for the first move.- Why interviewers like it: the naive state is always writable and always too big, so collapsing it is the visible skill.
Order: Longest Increasing Path in a Matrix → Minimum Distance to Type a Word Using Two Fingers → Filling Bookcase Shelves → Maximum Profit in Job Scheduling.
Core idea: When you type letter
i, one finger just typed letteri-1and the other is parked somewhere. You only ever need to remember where the parked finger is, the active finger's position is pinned toword[i-1]. So the state is(i, other)= "next letter to type" plus "position of the other finger." At each letter you decide which finger reaches for it, paying that finger's travel.
Problem, rephrased
You're building the input planner for a tablet's soft keyboard: the keys A–Z sit on a fixed grid, and the user types with two thumbs. You're given a string word to type. Each uppercase letter has a fixed cell, for letter ch, let k = ord(ch) - ord('A'); its position is (row, col) = (k // 6, k % 6), and sliding a thumb from cell (r1, c1) to (r2, c2) costs the Manhattan distance |r1 - r2| + |c1 - c2| in effort.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson