DP Window Optimisation

When To Use

Use this when a DP transition asks for min or max over a moving valid range.

Template

for i = 0; i < n; i++:
    expire invalid candidates from front
 
    dp[i] uses dq.front
 
    while dq not empty and candidate at dq.back is worse than i:
        pop back
 
    push i

The deque stores candidate indices, not raw values.

Problems

Constrained Subsequence Sum

Problem: maximize subsequence sum where consecutive chosen indices differ by at most k.

Pattern: dp[i] = nums[i] + max(0, max dp[j] in last k).

Applied pseudocode:

for i = 0; i < n; i++:
    while dq not empty and dq.front < i - k:
        dq.pop_front()
 
    best = dq empty ? 0 : max(0, dp[dq.front])
    dp[i] = nums[i] + best
 
    while dq not empty and dp[dq.back] <= dp[i]:
        dq.pop_back()
 
    dq.push_back(i)

Jump Game VI

Problem: maximize score when each jump can move at most k.

Pattern: fixed-range max DP.

Minimum Number of Coins for Fruits

Problem: minimum cost to buy fruits where buying one fruit grants a future range for free.

Pattern: min DP over a changing valid range.

Delivering Boxes From Storage to Ports

Problem: minimize trips subject to max boxes and max weight per delivery.

Pattern: min DP candidate under sliding feasibility constraints.

Max Value of Equation

Problem: maximize yi + yj + |xi - xj| where xj - xi <= k.

Pattern: maintain max yi - xi among valid previous points.