Skip to main content

Pattern 16: DP Optimizations

Advanced Optimization Techniques: Space optimization, monotonic queue, divide & conquer optimization, convex hull trick, Knuth optimization.

The Core Pattern​

THE MENTAL MODEL

Imagine making your DP solutions faster and more memory-efficient:

  1. Basic DP works but is too slow (TLE) or uses too much space (MLE)
  2. Apply advanced techniques to optimize time or space
  3. Different techniques for different DP patterns
  4. Can reduce O(n²) to O(n log n) or O(n)
  5. Can reduce O(n) space to O(1)

This is DP Optimization.

Common Optimization Techniques​

OPTIMIZATION TOOLBOX

Space Optimization

  • Reduce from 2D to 1D array
  • Rolling array (only keep last k rows)
  • Two variables instead of array
  • Example: Fibonacci, Knapsack

Monotonic Queue/Deque

  • Maintain useful candidates in deque
  • Remove suboptimal elements
  • Sliding window maximum pattern
  • Example: Jump Game variants, Maximal Rectangle

Divide & Conquer Optimization

  • When transitions have special structure
  • Split range and solve recursively
  • Reduces O(n³) to O(n² log n) or O(n²)
  • Requires quadrangle inequality

Convex Hull Trick

  • When choosing from linear functions
  • Maintain convex hull of lines
  • Query optimal line for given x
  • Reduces O(n²) to O(n log n) or O(n)

Knuth Optimization

  • For interval DP with monotonic optimal splits
  • opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]
  • Reduces O(n³) to O(n²)
  • Example: Optimal BST

Common Problems​

Space Optimization​

  • Climbing Stairs (O(1) space)
  • House Robber (O(1) space)
  • Coin Change (1D instead of 2D)

Monotonic Queue​

  • Sliding Window Maximum
  • Jump Game VI
  • Shortest Subarray with Sum at Least K

Convex Hull Trick​

  • Minimum Cost to Merge Stones (optimized)

Knuth Optimization​

  • Optimal Binary Search Tree
  • Stone Game variants

(Detailed examples will be added here)

When to Apply Optimizations​

OPTIMIZATION DECISION TREE

  1. Does base solution work?

    • Yes → Don't optimize yet
    • No → Check what's limiting

  2. What's the bottleneck?

    • Time (TLE) → Apply time optimizations
    • Space (MLE) → Apply space optimizations

  3. Which optimization?

    • See duplicate calculations → Memoization
    • 2D DP with only last row needed → Rolling array
    • Choosing from many transitions → Monotonic structure?
    • Range DP with O(n³) → Check Knuth property
    • Linear functions to choose from → Convex hull trick

Summary​

WHEN TO OPTIMIZE

Don't optimize prematurely!

  1. First get working solution
  2. Identify bottleneck (time/space)
  3. Apply appropriate technique
  4. Verify correctness

Most common: Space optimization (2D → 1D)

(More detailed examples and implementations will be added here)