Advanced DP design

A single-axis DP tracks one thing: an index in a string, a position in a grid, a count of items taken. Senior problems often need two things at once, and the second thing changes what "the previous state" even means. This lesson covers two patterns that show up again and again: a DP state with an extra resource dimension, and a DP transition that needs the best of several recent states instead of just one.

A second dimension: position and a resource limit

Say you have items, each with a position, a weight, and a value. You want to pick a subset that keeps total weight within a limit while maximizing total value. Sort the items by position, and let dp[w] be the best value reachable with total weight at most w. Each item, taken in position order, either adds to some capacities or leaves them alone.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    n = int(input_data[0])7    limit = int(input_data[1])8
9    items = []10    for i in range(n):11        pos = int(input_data[2 + i * 3])12        weight = int(input_data[2 + i * 3 + 1])13        value = int(input_data[2 + i * 3 + 2])14        items.append((pos, weight, value))15
16    items.sort()17
18    # dp[w] = maximum value using total weight at most w19    dp = [0] * (limit + 1)20
21    for pos, weight, value in items:22        if weight <= limit:23            for w in range(limit, weight - 1, -1):24                dp[w] = max(dp[w], dp[w - weight] + value)25
26    print(max(dp))27
28
29if __name__ == "__main__":30    main()

3 10
1 2 10
3 3 15
5 4 20

45

Sort the items first: weight 2 for value 10, weight 3 for value 15, and weight 4 for value 20, with a weight limit of 10. After the first item, every capacity from 2 up to 10 can already reach 10, because a single item of weight 2 fits inside any of them. After the second item, a capacity of 9 or more can fit both the first and second items, for 25. After the third item, a capacity of 9 or 10 fits all three, for 45, which is the best any capacity reaches. The inner loop runs from the limit down to the item's weight, so an item is never used twice in the same pass.

This is one dimension of state (w) updated once per item in sorted order. When a problem adds a real second dimension, such as dp[position][resource], the same idea applies: sort by position, then update the resource dimension for each position in turn, and keep only the best value for states that collide.

A window maximum inside the transition

Some DP transitions look back at a window of recent positions instead of a single one. "What is the best total ending within k positions of here?" turns every transition into a range maximum, and scanning the window each time costs O(k) per step, or O(nk) overall.

A monotonic dequemonotonic dequeA double-ended queue maintaining elements in monotonic order to track sliding window maximum.In the glossary answers that question in O(1). Keep the deque holding indices whose DP values are decreasing from front to back. The front is always the best value in the current window.

1import sys2from collections import deque3
4
5def main() -> None:6    input_data = sys.stdin.read().split()7    n = int(input_data[0])8    k = int(input_data[1])9    values = list(map(int, input_data[2:2 + n]))10
11    # dp[i] = the best total you can reach by ending your chosen positions at i.12    # Every earlier chosen position j in [i - k, i - 1] is a legal predecessor.13    dp = [0] * n14    dq = deque()  # indices j, kept so dp[j] is decreasing front to back15
16    for i in range(n):17        # Drop predecessors that fall outside the window before reading the front.18        while dq and dq[0] < i - k:19            dq.popleft()20
21        best_predecessor = dp[dq[0]] if dq else 022        dp[i] = values[i] + best_predecessor23
24        # dp[i] is now a candidate predecessor for later positions. Pop any25        # weaker entries at the back before adding it, so the deque stays26        # decreasing and the front is always the current window's best.27        while dq and dp[dq[-1]] <= dp[i]:28            dq.pop()29        dq.append(i)30
31    print(max(dp) if dp else 0)32
33
34if __name__ == "__main__":35    main()

5 2
5 10 3 8 2

28

Walk through it with values = [5, 10, 3, 8, 2] and k = 2. Position 0 has no predecessor, so dp[0] is just 5. Position 1 can follow position 0 (one step back, inside the window), giving dp[1] = 10 + 5 = 15. Position 2 follows position 1 for 3 + 15 = 18, position 3 follows position 2 for 8 + 18 = 26, and position 4 follows position 3 for 2 + 26 = 28. Because every position here is within one step of the last, the chain never breaks, and the deque always hands back the immediately preceding value without a scan. Each position pops any weaker entries off the back of the deque before it is added, so the entries that remain are always decreasing, and the one at the front is always the largest.

A boundary that only moves forward

A different kind of transition compares the current position against a moving boundary. The question is: what is the latest earlier position that still satisfies some condition against position i? If that boundary only moves forward as i increases, a single pointer can sweep across the whole array once. It never has to search for the boundary again at every position.

This comes up in interval scheduling sorted by start time: the latest earlier interval whose end is at or before the current interval's start never moves backward as you scan forward, because start times only increase. Rather than binary-searching for that boundary at each step, which costs O(log n) per position, you advance one pointer alongside the main loop and let it hold its place between positions. The whole sweep costs O(n) once both loops have run to the end. Not every moving boundary behaves this way. Check that the condition is genuinely monotonic in the sort order before you rely on a single forward pointer; if it can move backward, you need a binary search or a different structure such as a segment tree instead.

Optimizing Python for these DPs

Senior problems often have tight time limits, and Python needs deliberate optimization to fit inside them.

Use a rolling array when the current row of a DP only depends on the row before it. Keep two 1D arrays, current and previous, and swap them after each step, instead of storing a full 2D table. This turns O(n * m) memory into O(m), and PyPy's optimizer handles flat arrays much better than nested ones.

For sorting by several keys, build tuples and let Python's built-in sort handle them directly: sorted(items, key=lambda x: (x[2], x[0], -x[1])) sorts by the third field first, then the first, then the second in reverse. Tuple comparison in Python is implemented in C and is far faster than a custom comparator.

Prefer flat lists with integer indices over dictionaries for a rectangular state space. If a state has two components, compute a single index such as row * width + col and index into one flat list. Dictionary lookups carry hashing overhead that a flat list avoids entirely.

Common mistakes

Scanning a window naively inside the DP loop is the most common way to blow the time limit. If the loop over positions is O(n) and each transition scans O(k) predecessors, the total cost is O(nk), which can be too slow when k is close to n. A monotonic deque turns that into O(n) total, since each index enters and leaves the deque at most once.

A second mistake is allocating a full 2D table when only the current and previous rows are ever read. If dp[i][w] only depends on dp[i-1][w], two 1D arrays and a swap after each row use far less memory and run faster.

A third mistake is skipping the base case for the first position. If dp[0] needs special handling, such as no predecessor being available yet, make sure the code sets that up explicitly instead of letting an out-of-range access silently return zero or corrupt the rest of the table.

Finally, do not assume an approach is fast enough without measuring it on the largest input the problem allows. If a submission is close to the time limit, profile which part is slow: the DP transitions, the sort, or the input parsing. A correct O(n log n) algorithm can still fail on constant factors that Python is not forgiving about.

Recap

Combining a resource dimension with a position sorted DP, replacing a window scan with a monotonic deque, and recognizing a boundary that only moves forward are the three moves that make senior-level DP problems tractable. Rolling arrays, tuple sorts, and flat lists keep the Python implementation fast enough to use them.