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 — 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 positions at every index. It does not. After typing word[i−1], one of the fingers is necessarily on word[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.

The one-line idea: 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 alternative is a topological sort by value, which is the same computation arranged differently and useful to mention.

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).

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.

4. When the transition is a binary search

jobs = sorted(zip(end, start, profit))
ends, dp = [0], [0]                            # both strictly increasing
for e, s, p in jobs:
    i = bisect_right(ends, s) - 1              # last job finishing at or before s
    if dp[i] + p > dp[-1]:
        ends.append(e); dp.append(dp[i] + p)
return dp[-1]

Sorting by end time is what makes ends increasing and therefore searchable. dp is kept monotonic by appending only when the new total beats the current best, which means dp[-1] is always the answer so far and no final scan is needed.

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 — always make the cheapest move now:
  C   place a finger there                                  0
  A   same finger C→A = 2   vs   place the other finger = 0  → 0
  K   fingers on C and A:  C→K = 3   vs   A→K = 5            → 3
  E   fingers on K and A:  K→E = 1   vs   A→E = 4            → 1
                                                    total    4

the optimum — split the word between the fingers:
  finger 1 types C then A        C→A = 2
  finger 2 types K then E        K→E = 1
                                                    total    3

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 engines. Filling shelves is the same recurrence as breaking a paragraph into lines under a width limit.
• Revenue management. Weighted job scheduling underlies ad slots, meeting rooms and rental bookings.
• Terrain and hydrology. Longest increasing path is water flow over a height map.
• Input and accessibility research. Two-thumb typing cost is a genuine keyboard-layout metric.
• 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. Memoised DFS — the increase rule makes cycles impossible, so no visited set is needed.
Pattern: memoised DFS on an implicit DAG. Target: O(mn) time and space.

▶ Minimum Distance to Type a Word Using Two Fingers

Least total finger travel. 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.

▶ Filling Bookcase Shelves

Least total height with books kept in order. For each prefix, try every contiguous suffix as the last shelf.
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.
• 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_left on the ends array, which admits a job that ends exactly when the next begins — or excludes one that should qualify. Check the boundary against the problem's definition.
• Memoising on mutable state. Keys must be the position and the small extra coordinate, nothing else.

9. Key takeaways

1. State = position + the smallest thing you must remember. Anything implied is not state.
2. A strict-increase rule gives you a DAG for free — no visited set, no cycle handling.
3. Contiguity is a gift. "Books stay in order" is what makes the shelf a suffix.
4. Sort to make a transition searchable. By end time, then bisect.
5. Keeping a DP array monotonic means the answer is always its last element.
6. None as an initial position removes the special case for the first move.
7. 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.