DP optimisations — prefix sums, a monotonic deque and bitmasks

Q: What is a monotonic deque in dynamic programming?

A deque of indices whose dp values decrease from front to back. Before pushing index i, pop every back entry with a value no larger than dp[i] — it can never be the maximum again — and pop the front when it leaves the window. The front is then the window's maximum, and each index is pushed and popped once, O(n) in all.

Q: How do prefix sums speed up a DP transition?

If dp[i][k] = dp[i−1][k−c] + … + dp[i−1][k], the sum over a contiguous range of the previous row, build prefix sums P of that row once and read the range as P[k+1] − P[k−c]. The transition drops from O(c) to O(1), so the table costs O(n·K) instead of O(n·K·c). Take the difference modulo the prime, plus the prime.

Q: What is bitmask DP?

Dynamic programming whose state includes a subset of up to about 20 items stored as the bits of an integer: bit j set means item j is used. The travelling-salesman DP dp[mask][v], the cheapest path visiting exactly mask and ending at v, has 2^n · n states and n transitions each — O(2^n · n²), which is about 600,000 steps at n = 12.

Q: When is bitmask DP feasible?

When the set being chosen from has at most about 20 elements. 2^20 is about 10^6 masks; times n states per mask and n transitions, n ≤ 16 to 18 is the usual ceiling for O(2^n · n²), and n ≤ 20 to 22 for O(2^n · n).

16 min · +10 XP · 2 exercises · 4 questions

Read the text16 min

Exercises0/2

Quiz4 q

Quick answer

How do you optimise a dynamic programming solution?

Look at the transition, not the states. When each state sums a contiguous range of the previous row, keep prefix sums of that row and read the range in O(1). When it takes the maximum over a sliding window, keep a monotonic deque of candidates. Both remove a factor of k from O(n·k). For exponential problems on n ≤ 20, a bitmask indexes the subsets.

A DP is states × transition cost. The states are usually fixed by the problem; the transition is where the speed hides. If one state reads a whole window of earlier states, the loop is O(n · k) — and 10⁵ × 10⁵ does not fit.

Prefix sums: a range of the previous row in O(1)

Count the ways to share K sweets between n children when child i takes 0..cᵢ:

dp[i][k] = dp[i−1][k−cᵢ] + … + dp[i−1][k] — a contiguous range of the previous row.
Build prefix sums P of row i−1 once, then dp[i][k] = P[k+1] − P[max(0, k−cᵢ)].
O(n · K · c) becomes O(n · K). Under a modulus, add the prime before taking %.

Prefix sums make each DP cell one subtraction

caps = [1, 2, 3], K = 4

dp[i][k] counts the ways to give k sweets to the first i children. With no children there is one way to give 0 sweets and none to give more: row 0 is 1, 0, 0, 0, 0.

0:01 / 0:22Step 1 of 7

Transcript · 7 steps

A monotonic deque: the maximum of a sliding window

Jump through an array, at most k cells at a time, maximising the sum of the cells you land on: dp[i] = a[i] + max(dp[i−k..i−1]).

Keep a deque of indices whose dp values decrease from front to back.
Pop the front when it falls out of the window; read the maximum there.
Before pushing i, pop every back index with dp ≤ dp[i]: it is older and no better, so it can never win again.
Each index enters and leaves once: O(n) instead of O(n · k).

A monotonic deque keeps the window's maximum at its front

a = [1, -1, -2, 4, -7, 3], k = 2

dp[i] is the best score standing on cell i, moving 1 to 2 cells at a time: dp[i] = a[i] + the maximum of the last 2 dp values. Start with dp[0] = 1 and index 0 in the deque.

0:01 / 0:22Step 1 of 6

Transcript · 6 steps

deque<int> dq{0};
for (int i = 1; i < n; ++i) {
    while (dq.front() < i - k) dq.pop_front();       // left the window
    dp[i] = a[i] + dp[dq.front()];                    // the window's best
    while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
    dq.push_back(i);
}

Bitmasks: DP over subsets

When n ≤ 20, a subset fits in an int: bit j set means item j is taken.

dp[mask][v] = cheapest path that has visited exactly mask and stands at v.
Transition: for each u not in mask, relax dp[mask | 1 << u][u].
2ⁿ · n states, n moves each: O(2ⁿ · n²) — 600 000 steps at n = 12, 8.5 × 10⁷ at n = 18.

More practice

Common questions

What is a monotonic deque in dynamic programming?

A deque of indices whose dp values decrease from front to back. Before pushing index i, pop every back entry with a value no larger than dp[i] — it can never be the maximum again — and pop the front when it leaves the window. The front is then the window's maximum, and each index is pushed and popped once, O(n) in all.

How do prefix sums speed up a DP transition?

If dp[i][k] = dp[i−1][k−c] + … + dp[i−1][k], the sum over a contiguous range of the previous row, build prefix sums P of that row once and read the range as P[k+1] − P[k−c]. The transition drops from O(c) to O(1), so the table costs O(n·K) instead of O(n·K·c). Take the difference modulo the prime, plus the prime.

What is bitmask DP?

Dynamic programming whose state includes a subset of up to about 20 items stored as the bits of an integer: bit j set means item j is used. The travelling-salesman DP dp[mask][v], the cheapest path visiting exactly mask and ending at v, has 2^n · n states and n transitions each — O(2^n · n²), which is about 600,000 steps at n = 12.

When is bitmask DP feasible?

When the set being chosen from has at most about 20 elements. 2^20 is about 10^6 masks; times n states per mask and n transitions, n ≤ 16 to 18 is the usual ceiling for O(2^n · n²), and n ≤ 20 to 22 for O(2^n · n).

Mark as readSign in to keep your place.

DP Optimization Techniques in C++: Prefix Sums, Deque, Bitmask

Speed up a DP transition: prefix sums for range sums of the previous row, a monotonic deque for a sliding-window maximum, and bitmask DP for subsets.

Course: Competitive Programming study plan
Module: DP optimisations
Kind: Lesson
Reading time: 16 min
Runtime: Clang 18 · C++20

How do you optimise a dynamic programming solution?

Lesson

Prefix sums: a range of the previous row in O(1)

Count the ways to share K sweets between n children when child i takes 0..cᵢ:

dp[i][k] = dp[i−1][k−cᵢ] + … + dp[i−1][k] — a contiguous range of the previous row.
Build prefix sums P of row i−1 once, then dp[i][k] = P[k+1] − P[max(0, k−cᵢ)].
O(n · K · c) becomes O(n · K). Under a modulus, add the prime before taking %.

Prefix sums make each DP cell one subtraction. Example: caps = [1, 2, 3], K = 4

dp[i][k] counts the ways to give k sweets to the first i children. With no children there is one way to give 0 sweets and none to give more: row 0 is 1, 0, 0, 0, 0.
Child 1 takes 0..1, so dp1[k] sums dp0[k−1..k]. Build prefix sums P of row 0 once; then dp1[1] = P2 − P0 = 1 − 0 = 1, one subtraction instead of 2 additions.
Every cell of row 1 is one such subtraction: 1, 1, 0, 0, 0. The row costs O(K), not O(K · c).
Child 2 takes 0..2, so dp2[k] sums dp1[k−2..k]. Build prefix sums P of row 1 once; then dp2[3] = P4 − P1 = 2 − 1 = 1, one subtraction instead of 3 additions.
Every cell of row 2 is one such subtraction: 1, 2, 2, 1, 0. The row costs O(K), not O(K · c).
Child 3 takes 0..3, so dp3[k] sums dp2[k−3..k]. Build prefix sums P of row 2 once; then dp3[4] = P5 − P1 = 6 − 1 = 5, one subtraction instead of 4 additions.
Row 3 is 1, 3, 5, 6, 5: there are 5 ways to share 4 sweets with caps 1, 2, 3. The table cost O(n · K) in all.

A monotonic deque: the maximum of a sliding window

Jump through an array, at most k cells at a time, maximising the sum of the cells you land on: dp[i] = a[i] + max(dp[i−k..i−1]).

Keep a deque of indices whose dp values decrease from front to back.
Pop the front when it falls out of the window; read the maximum there.
Before pushing i, pop every back index with dp ≤ dp[i]: it is older and no better, so it can never win again.
Each index enters and leaves once: O(n) instead of O(n · k).

A monotonic deque keeps the window's maximum at its front. Example: a = [1, -1, -2, 4, -7, 3], k = 2

dp[i] is the best score standing on cell i, moving 1 to 2 cells at a time: dp[i] = a[i] + the maximum of the last 2 dp values. Start with dp[0] = 1 and index 0 in the deque.
i = 1: the front, index 0, gives the window's best 1, so dp[1] = -1 + 1 = 0. Nothing at the back is beaten, so 1 joins behind.
i = 2: the front, index 0, gives the window's best 1, so dp[2] = -2 + 1 = -1. Nothing at the back is beaten, so 2 joins behind.
i = 3: index 0 left the window and was dropped from the front; the front, index 1, gives the window's best 0, so dp[3] = 4 + 0 = 4. Indexes 2 and 1 are no better than 4 and older, so they are popped from the back before 3 is pushed.
i = 4: the front, index 3, gives the window's best 4, so dp[4] = -7 + 4 = -3. Nothing at the back is beaten, so 4 joins behind.
i = 5: the front, index 3, gives the window's best 4, so dp[5] = 3 + 4 = 7. Indexes 4 and 3 are no better than 7 and older, so they are popped from the back before 5 is pushed. The answer is dp[5] = 7.

deque<int> dq{0};
for (int i = 1; i < n; ++i) {
    while (dq.front() < i - k) dq.pop_front();       // left the window
    dp[i] = a[i] + dp[dq.front()];                    // the window's best
    while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
    dq.push_back(i);
}

Bitmasks: DP over subsets

When n ≤ 20, a subset fits in an int: bit j set means item j is taken.

dp[mask][v] = cheapest path that has visited exactly mask and stands at v.
Transition: for each u not in mask, relax dp[mask | 1 << u][u].
2ⁿ · n states, n moves each: O(2ⁿ · n²) — 600 000 steps at n = 12, 8.5 × 10⁷ at n = 18.

More practice

Common questions

What is a monotonic deque in dynamic programming?

How do prefix sums speed up a DP transition?

What is bitmask DP?

When is bitmask DP feasible?

Exercises

Jumps within a window

You stand on cell 1 of a row of n cells and must reach cell n. Each move goes forward by 1 to k cells. Your score is the sum of a[i] over every cell you stand on, the first and the last included. Print the largest possible score.

dp[i] = a[i] + max(dp[i−k..i−1]) is O(n · k); keep a monotonic deque of indices with decreasing dp values to make it O(n).

Constraints: 1 ≤ n, k ≤ 10^5, |a[i]| ≤ 10^4. Input: n k, then the n values. Output: the best score.

6 2
1 -1 -2 4 -7 3

prints 7 — the cells 1, −1, 4, 3.

Sharing sweets with caps

Share exactly K identical sweets among n children so that child i gets between 0 and a[i] sweets. Print the number of ways modulo 10^9 + 7.

dp[i][k] = dp[i−1][k−a[i]] + … + dp[i−1][k] is a contiguous range of the previous row: keep its prefix sums so each state costs O(1), and the whole table O(n · K).

Constraints: 1 ≤ n ≤ 100, 0 ≤ K ≤ 10^5, 0 ≤ a[i] ≤ K. Input: n K, then a[1..n]. Output: the count modulo 1 000 000 007.

3 4
1 2 3

prints 5: (0, 1, 3), (0, 2, 2), (1, 0, 3), (1, 1, 2) and (1, 2, 1).

In this module: DP optimisations

← Checkpoint — Segment trees and Fenwick trees · Checkpoint — DP optimisations →