dp-optimizer

name	dp-optimizer
description	Apply advanced DP optimizations automatically
allowed-tools	["Read","Write","Grep","Glob","Edit"]
graph	{"domains":["domain:computer-science"],"specializations":["specialization:algorithms-optimization"],"skillAreas":["skill-area:dynamic-programming"],"roles":["role:backend-engineer","role:computational-scientist"]}

DP Optimizer Skill

Purpose

Apply advanced dynamic programming optimizations to improve time and space complexity of DP solutions.

Capabilities

• Convex hull trick detection and application
• Divide and conquer optimization
• Knuth optimization
• Monotonic queue/deque optimization
• Alien's trick / WQS binary search
• Rolling array optimization
• Bitmask compression

Target Processes

• dp-state-optimization
• advanced-dp-techniques
• complexity-optimization

Optimization Techniques

Time Optimizations

1. Convex Hull Trick: O(n^2) -> O(n log n) for certain recurrences
2. Divide & Conquer: O(n^2 k) -> O(n k log n) when optimal j is monotonic
3. Knuth Optimization: O(n^3) -> O(n^2) for certain interval DP
4. Monotonic Queue: O(n*k) -> O(n) for sliding window DP

Space Optimizations