Skip to content
Tutorials Center
My learning

Topics

Lesson 160 of 225 ยท Dynamic Programming

Optimising DP

Speed up and shrink dynamic programming in Python: rolling arrays, prefix-sum speedups, monotonic deque optimisation and a map of the named DP optimisations.

You have written a correct DP. It passes the small examples and then fails the big ones, either with a memory error or a time limit. The good news is that a correct DP is a great starting point: its structure tells you where the waste hides. This lesson covers the optimisations that work again and again, ordered from the easiest and most common to the advanced techniques you should at least recognise by name.

There are two different problems to fix. Space problems ("the table does not fit") are usually solved by keeping only the part of the table you still need. Time problems ("too many transitions per state") are solved by computing each transition's work with a smarter data structure. A third question comes first: is the state itself too big?

1. Rolling arrays: keep only what you need

Many tables fill row by row, and row i only looks at row i - 1. Then rows older than that can be thrown away, and an O(n * m) table shrinks to O(m) with the same running time.

TEXT
LCS table, filled row by row:

        row i-1:  [ . . . . . . ]
                        |  \
        row i  :  [ . . x . . . ]      x needs only the cell above,
                                        the cell to the left and the diagonal
Python LCS with two rows instead of the full table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second number in each pair is the count of stored cells. Two rows give the same answer with far fewer cells. The price: you lose the old rows, so you cannot walk the table backwards to reconstruct the actual subsequence. If you need the solution itself and not just its value, keep the full table, or use a divide-and-conquer trick (Hirschberg's algorithm) that rebuilds it from rolling rows.

One row is enough for knapsack

In the 0/1 knapsack, dp[i][w] needs only dp[i-1][w] and dp[i-1][w - weight]. Both come from the previous item, so a single array works if you loop the capacity downward. Going downward means dp[w - weight] has not yet been updated for the current item, so each item is used at most once.

Python Knapsack in one array: downward versus upward loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The upward loop solves a different problem: unbounded knapsack, where an item may be taken many times. Same code, opposite loop direction, different meaning; this is a famous source of bugs. See coin change for the unbounded flavour.

2. Prefix sums: speed up "sum over a range of previous states"

Often the transition is dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k], a sum over a window of earlier states. Computing each window from scratch costs O(k). But neighbouring windows overlap almost completely, so a prefix sum (or a running window sum) gives each in O(1).

Example: in how many ways can you roll d dice with k faces each so that the total is exactly target? With dp[i][s] = ways to reach sum s with i dice, we have dp[i][s] = sum of dp[i-1][s-f] for f in 1..k.

Python Dice sums: naive window versus running window sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive version does about d * target * k additions; the window version does d * target. The factor k disappeared. The same trick speeds up counting partitions, "number of ways to climb stairs with up to k steps", and many probability DPs.

3. A monotonic deque for "best of the last k states"

When the transition is dp[i] = cost[i] + max(dp[i-k .. i-1]), a prefix sum cannot help because max is not subtractable. But a monotonic deque (see deques and monotonic queues) keeps the maximum of a sliding window in amortised O(1).

Problem: you stand on cell 0 of an array of scores. Each move jumps 1 to k cells forward. You collect the score of every cell you land on and must end on the last cell. Maximise the total.

Brute force DP: dp[i] = nums[i] + max(dp[i-k..i-1]) costs O(n * k). Optimised: the deque stores indexes whose dp values are decreasing; the front is always the best of the window.

Python Jump with at most k steps: loop versus monotonic deque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each index enters and leaves the deque at most once, so the total is O(n) regardless of k. Compare the two operation counts in the output: the deque version is smaller by a large factor.

4. Named optimisations you should recognise

Competitive programmers have names for a family of "reduce the transition cost" tricks. You rarely need them in interviews, but you should know what problem each solves, so you can search for the right one.

Technique Applies to Idea Typical gain
Rolling array row-by-row tables keep only the last 1-2 rows O(nm) space to O(m)
Prefix sums / running sum sum over a window of states update window in O(1) O(nk) to O(n) time
Monotonic queue max/min over a sliding window of states deque of candidates O(nk) to O(n)
Binary search on dp values LIS and similar bisect over a sorted tails array O(n^2) to O(n log n); see LIS
Convex hull trick dp[i] = min(dp[j] + b[j] * a[i]), lines in a[i] keep lower envelope of lines O(n^2) to O(n log n) or O(n)
Divide and conquer optimisation dp[i][j] = min over k (dp[i-1][k] + cost(k, j)) when the best k is monotone in j recurse on the middle, narrow the k range O(kn^2) to O(kn log n)
Knuth optimisation interval DPs like optimal BST, when opt[i][j-1] <= opt[i][j] <= opt[i+1][j] bound the split point O(n^3) to O(n^2); see interval DP
SOS (sum over subsets) DP sums over all submasks process one bit at a time O(3^n) to O(n * 2^n); see bitmask DP
Bitset boolean DPs such as subset-sum pack 64 states per word up to 64x faster

You can already use one of these in Python without extra theory: a boolean subset-sum DP stored as one big integer, where "shift and OR" processes every sum at once.

Python Subset sum with a Python integer as a bitset

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The single bits |= bits << x line replaces the whole inner loop, and Python's big integers do the shifting a word at a time in C.

5. Choosing the state well

The best optimisation is often a better state. Before you reach for a heavy technique, ask:

  • Do I need every dimension? If dp[i][j] only depends on i - j or on i + j, one index is redundant.
  • Is one dimension a function of the others? In many string and grid problems the number of items used is determined by position.
  • Can I swap value and index? Knapsack with huge weights but small values can be run over value instead (dp[value] = minimum weight).
  • Can I trade the state for the answer? In LIS, "the smallest tail of an increasing subsequence of length L" is a better state than "the best subsequence ending at i".
  • Is the order forced? Sorting first (by end time, by weight) often removes a dimension.

Optimise in this order: (1) make it correct with simple memoization, (2) count the states and the work per state, (3) fix whichever factor is too big, (4) only then compress memory. Measuring operations first stops you from optimising the wrong thing.

Common mistakes

  • Rolling over a dependence you still need. If dp[i] also reads dp[i-2] or a column to the right, two rows may not be enough. List exactly which cells each cell reads.
  • Wrong loop direction in a one-dimensional knapsack (downward for 0/1, upward for unbounded).
  • Off-by-one in a window sum. Whether dp[s-k] or dp[s-k-1] leaves the window is the whole bug; test with a tiny k.
  • Forgetting to expire deque indexes. Pop from the front when the index leaves the window, or the answer silently uses stale states.
  • Losing reconstruction. Compressed memory cannot rebuild the solution unless you also store choices.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A DP fills row i using only row i-1. How much memory do you need for the table values?

    Keeping only the previous and current rows is enough. The running time stays the same.
  2. 2. In the one-array 0/1 knapsack, why must the capacity loop go downward?

    An upward loop would see already-updated cells and could take the same item several times (unbounded knapsack).
  3. 3. dp[i] = cost[i] + max(dp[i-k .. i-1]). Which tool gives O(n) total time?

    Prefix sums handle sums, not maximums. A monotonic deque keeps the window maximum in amortised O(1).
  4. 4. What do you lose when you compress a 2D DP to two rows?

    The final value is unaffected, but the old rows that a backtrack would need are gone.
  5. 5. Which technique turns the dice-sum transition from O(k) per state to O(1)?

    Adjacent windows share k-1 terms: add the new state and subtract the one that left.

Summary

  • First fix the state and the recurrence; then optimise space, then time.
  • Rolling arrays keep 1 or 2 rows; the cost is losing easy reconstruction. One-array knapsack loops downward for 0/1 and upward for unbounded.
  • Window sums and prefix sums remove a factor k from "sum of the last k states" transitions.
  • A monotonic deque does the same for "max or min of the last k states".
  • Named techniques (convex hull trick, divide and conquer, Knuth, SOS, bitsets) are for specific transition shapes; know the names and where they apply.
  • Always count operations before and after to confirm the optimisation did what you meant.

Next: Greedy Algorithms