Phase 6 covered DP as a modeling discipline: pick the right state, write the recurrence, fill the table. This page is about a different question — once the recurrence is right, can it run faster? A handful of named optimizations turn an $O(n^2)$ or $O(n^3)$ transition into something close to linear, by exploiting extra structure (monotonicity, convexity) that the naive recurrence doesn’t use. This is not an exhaustive list — competitive programming has a deep well of these — but the ones below cover the techniques that actually show up repeatedly.

What you’ll learn

• Digit DP: counting how many numbers up to NN satisfy a per-digit property, without ever enumerating the numbers themselves.
• A pointer back to bitmask DP (Phase 6) for the subset-state family of optimizations.
• Monotonic-deque-optimized DP: when a transition needs “the best DP value in a sliding window,” a deque keeps that lookup $O(1)$ amortized instead of $O(k)$.
• A conceptual tour of three further speedups — the convex hull trick, divide-and-conquer DP, and Knuth’s optimization — and the shape of recurrence each one targets.

Digit DP: counting without enumerating

Some problems ask “how many integers from 00 to NN satisfy some per-digit property” where NN can be astronomically large (10^1810^18). Enumerating every number is impossible, but the property only ever depends on which digits appear and whether the number built so far is still capped by NN’s own digits — so the DP state is (position, tight)(position, tight), where tighttight means “every digit chosen so far exactly matches NN’s digits” (so the next digit is capped) versus “already strictly smaller” (so the next digit can be anything 0-90-9).

from functools import lru_cache
 
 
def count_without_digit(n, forbidden):
    digits = [int(c) for c in str(n)]
 
    @lru_cache(maxsize=None)
    def dp(pos, tight):
        if pos == len(digits):
            return 1                          # built a full, valid number
        limit = digits[pos] if tight else 9    # capped only while still matching N's prefix
        total = 0
        for d in range(0, limit + 1):
            if d == forbidden:
                continue                       # this digit isn't allowed anywhere
            total += dp(pos + 1, tight and d == limit)
        return total
 
    result = dp(0, True)
    dp.cache_clear()                           # dp is only valid for THIS n's digit string
    return result
 
 
n = 50
result = count_without_digit(n, forbidden=4)
brute_force = sum(1 for x in range(n + 1) if "4" not in str(x))
print("digit DP:", result)
print("brute force (sanity check):", brute_force)

from functools import lru_cache
 
 
def count_without_digit(n, forbidden):
    digits = [int(c) for c in str(n)]
 
    @lru_cache(maxsize=None)
    def dp(pos, tight):
        if pos == len(digits):
            return 1                          # built a full, valid number
        limit = digits[pos] if tight else 9    # capped only while still matching N's prefix
        total = 0
        for d in range(0, limit + 1):
            if d == forbidden:
                continue                       # this digit isn't allowed anywhere
            total += dp(pos + 1, tight and d == limit)
        return total
 
    result = dp(0, True)
    dp.cache_clear()                           # dp is only valid for THIS n's digit string
    return result
 
 
n = 50
result = count_without_digit(n, forbidden=4)
brute_force = sum(1 for x in range(n + 1) if "4" not in str(x))
print("digit DP:", result)
print("brute force (sanity check):", brute_force)

The state space is tiny — len(digits) * 2len(digits) * 2 states, each doing $O(10)$ work — so this counts numbers up to 10^1810^18 in about 20 states total, versus enumerating $10^{18}$ numbers directly.

Bitmask DP: already covered in Phase 6

The other major “state isn’t an index” family — bitmask DP, where the state is which subset of items has been used (Traveling Salesman being the canonical example) — is covered in depth in Bitmask and Tree DP back in Phase 6. If subset-shaped state is new to you, that’s the page to revisit; this lesson focuses on the optimizations that speed up an already-correct recurrence rather than the modeling itself.

Monotonic-deque-optimized DP

Some recurrences need, at each step, the best DP value within a sliding window of the last kk positions:

Computing that inner max naively costs $O(k)$ per step — $O(nk)$ total. A monotonic deque keeps the window’s maximum available in $O(1)$: push indices onto the back, but first pop off any index whose dpdp value is <=<= the new one (they can never be the answer again, since the new index is both more recent and at least as good), and pop stale indices off the front once they fall outside the window.

from collections import deque
 
 
def constrained_subset_sum(nums, k):
    n = len(nums)
    dp = [0] * n
    dq = deque()                          # holds indices, dp[dq[0]] .. dp[dq[-1]] decreasing
 
    for i in range(n):
        while dq and dq[0] < i - k:
            dq.popleft()                   # front index fell outside the window -- drop it
 
        best_prev = dp[dq[0]] if dq and dp[dq[0]] > 0 else 0
        dp[i] = nums[i] + best_prev
 
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()                       # a worse-or-equal, older candidate is now useless
        dq.append(i)
 
    return max(dp)
 
 
nums = [10, 2, -10, 5, 20, -7, -15]
k = 2
print("constrained subset sum:", constrained_subset_sum(nums, k))   # expect 37

from collections import deque
 
 
def constrained_subset_sum(nums, k):
    n = len(nums)
    dp = [0] * n
    dq = deque()                          # holds indices, dp[dq[0]] .. dp[dq[-1]] decreasing
 
    for i in range(n):
        while dq and dq[0] < i - k:
            dq.popleft()                   # front index fell outside the window -- drop it
 
        best_prev = dp[dq[0]] if dq and dp[dq[0]] > 0 else 0
        dp[i] = nums[i] + best_prev
 
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()                       # a worse-or-equal, older candidate is now useless
        dq.append(i)
 
    return max(dp)
 
 
nums = [10, 2, -10, 5, 20, -7, -15]
k = 2
print("constrained subset sum:", constrained_subset_sum(nums, k))   # expect 37

Every index enters and leaves the deque at most once, so the whole sliding-window maximum bookkeeping is $O(n)$ total — the deque turns an $O(nk)$ DP into an $O(n)$ one.

Further reading: three more named optimizations

These show up less often than digit DP or the monotonic-deque trick, but recognizing the recurrence shape that triggers each one is worth knowing even without memorizing the implementation.

Convex hull trick (CHT). Targets recurrences of the form

— read each jj as defining a line y = b_j \cdot x + dp[j]y = b_j \cdot x + dp[j], and dp[i]dp[i] as the minimum of all those lines evaluated at x = a_ix = a_i. Maintaining the lower envelope of the lines added so far (a monotonic stack of lines, popping ones that are never optimal) answers each query in $O(\log n)$ or even amortized $O(1)$ if the a_ia_i queries arrive in sorted order — turning an $O(n^2)$ recurrence into $O(n \log n)$.

Divide-and-conquer DP optimization. Targets 2D recurrences

where the optimal split point opt(i, j)opt(i, j) is monotonic in jj for a fixed ii (opt(i, j) \le opt(i, j+1)opt(i, j) \le opt(i, j+1)). Solving for the middle jj first, then recursing on the left and right halves with kk’s search range narrowed by that monotonicity, computes an entire DP row in $O(n \log n)$ instead of $O(n^2)$.

Knuth’s optimization. Targets interval DP recurrences

when costcost satisfies the quadrangle inequality. Under that condition, the optimal split opt(i, j)opt(i, j) satisfies opt(i, j-1) \le opt(i, j) \le opt(i+1, j)opt(i, j-1) \le opt(i, j) \le opt(i+1, j) — bounding each split point’s search range enough that the total work across the whole table drops from $O(n^3)$ to $O(n^2)$.

Complexity summary

Practice — real LeetCode problems

Three partition DPs. All three share one skeleton — split the array into kk consecutive groups, minimise the sum of group costs — and each adds a different twist: a running maximum, a divisibility constraint, and a precomputed cost matrix that opens the door to divide-and-conquer optimisation.

LC 1335 — Minimum Difficulty of a Job Schedule · Hard

Problem. Jobs must be done in order over exactly dd days, at least one job per day. A day’s difficulty is the maximum difficulty among its jobs; the schedule’s difficulty is the sum over days. Return the minimum, or -1-1 if impossible.

Constraints. 1 <= len(jobDifficulty) <= 3001 <= len(jobDifficulty) <= 300, 0 <= jobDifficulty[i] <= 10000 <= jobDifficulty[i] <= 1000, 1 <= d <= 101 <= d <= 10.

Examples. jobDifficulty = [6,5,4,3,2,1], d = 2jobDifficulty = [6,5,4,3,2,1], d = 2 gives 77 — day one takes the first five jobs (difficulty 6), day two takes the last (difficulty 1) · [9,9,9], d = 4[9,9,9], d = 4 gives -1-1 · [1,1,1], d = 3[1,1,1], d = 3 gives 33

LC 1000 — Minimum Cost to Merge Stones · Hard

Problem. Merge exactly kk consecutive piles into one at a cost equal to the total number of stones in those kk piles. Return the minimum cost to end with one pile, or -1-1 if impossible.

Constraints. 1 <= len(stones) <= 301 <= len(stones) <= 30, 2 <= k <= 302 <= k <= 30, 1 <= stones[i] <= 1001 <= stones[i] <= 100.

Examples. stones = [3,2,4,1], k = 2stones = [3,2,4,1], k = 2 gives 2020 · stones = [3,2,4,1], k = 3stones = [3,2,4,1], k = 3 gives -1-1 · stones = [3,5,1,2,6], k = 3stones = [3,5,1,2,6], k = 3 gives 2525

LC 1478 — Allocate Mailboxes · Hard

Problem. Given house positions on a street and kk mailboxes to place, return the minimum total distance between each house and its nearest mailbox.

Constraints. 1 <= k <= len(houses) <= 1001 <= k <= len(houses) <= 100, 1 <= houses[i] <= 10**41 <= houses[i] <= 10**4, all positions distinct.

Examples. houses = [1,4,8,10,20], k = 3houses = [1,4,8,10,20], k = 3 gives 55 · houses = [2,3,5,12,18], k = 2houses = [2,3,5,12,18], k = 2 gives 99

LeetCode problem set

Recap

• Digit DP: state (position, tight, ...extra)(position, tight, ...extra) counts numbers up to NN without enumerating them — extend the extra state to match whatever per-digit property the problem asks about.
• Bitmask DP (subset state) lives in Phase 6’s Bitmask and Tree DP — revisit that page for the modeling side of subset-shaped DP.
• Monotonic-deque DP turns an $O(nk)$ sliding-window-max transition into $O(n)$ by keeping the deque’s indices’ dpdp values decreasing.
• Convex hull trick, D&C DP optimization, and Knuth’s optimization each target a specific recurrence shape — lines evaluated at a point, a monotonic split point, and the quadrangle inequality, respectively — worth recognizing by name even without full fluency in the implementation.

That closes out the advanced-CP-topics phase — between string automatons, bit-level tricks, and these DP speedups, you now have the toolkit for the recurring “how do I make this fast enough” questions that separate CP problems from a typical coding interview.