dp-optimizer
npx machina-cli add skill a5c-ai/babysitter/dp-optimizer --openclawFiles (1)
SKILL.md
1.9 KB
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
- Convex Hull Trick: O(n^2) -> O(n log n) for certain recurrences
- Divide & Conquer: O(n^2 k) -> O(n k log n) when optimal j is monotonic
- Knuth Optimization: O(n^3) -> O(n^2) for certain interval DP
- Monotonic Queue: O(n*k) -> O(n) for sliding window DP
Space Optimizations
- Rolling Array: O(n*m) -> O(m) when only previous row needed
- Bitmask Compression: Reduce state space with bit manipulation
Input Schema
{
"type": "object",
"properties": {
"dpCode": { "type": "string" },
"stateDefinition": { "type": "string" },
"transitions": { "type": "string" },
"currentComplexity": { "type": "string" },
"targetComplexity": { "type": "string" },
"optimizationType": {
"type": "string",
"enum": ["auto", "convexHull", "divideConquer", "knuth", "monotonic", "space"]
}
},
"required": ["dpCode", "optimizationType"]
}
Output Schema
{
"type": "object",
"properties": {
"success": { "type": "boolean" },
"optimizedCode": { "type": "string" },
"optimizationApplied": { "type": "string" },
"newComplexity": { "type": "string" },
"explanation": { "type": "string" }
},
"required": ["success"]
}
Source
git clone https://github.com/a5c-ai/babysitter/blob/main/plugins/babysitter/skills/babysit/process/specializations/algorithms-optimization/skills/dp-optimizer/SKILL.mdView on GitHub Overview
DP Optimizer automatically applies advanced dynamic programming optimizations to improve time and space complexity of DP solutions. It detects patterns suitable for convex hull trick, divide-and-conquer, Knuth optimization, monotonic queues, rolling arrays, and bitmask compression, and applies them to your DP solutions.
How This Skill Works
It analyzes the DP code (dpCode), stateDefinition, and transitions, then selects an applicable optimization based on the recurrence and input constraints. When a technique fits, it rewrites the DP transitions or uses helper structures (lines for convex hull, partitioning for divide-and-conquer, rolling arrays for space) and outputs the optimized code along with the new theoretical complexity.
When to Use It
- Your recurrence has a monotone opt or candidate j that moves to the right, enabling Divide & Conquer or Knuth optimization.
- The recurrence is linear-quadratic or can be transformed with Convex Hull Trick.
- Memory is a bottleneck and you only need the previous DP row (Rolling Array).
- Your DP processes a sliding window or local optimum with small k, where Monotonic Queue helps.
- The state space is large but can be compressed with bitmasks or explored via Alien's Trick / WQS binary search.
Quick Start
- Step 1: Provide your DP code (dpCode), stateDefinition, and transitions, and specify current and target complexity.
- Step 2: Choose optimizationType (auto, convexHull, divideConquer, knuth, monotonic, space) and run the dp-optimizer.
- Step 3: Review optimizedCode and newComplexity, then validate correctness with tests.
Best Practices
- Benchmark current time and space before applying optimizations to avoid over-optimizing.
- Validate that the recurrence satisfies optimization prerequisites (convexity, monotonicity, quadrangle inequality).
- Start with rolling array or bitmask compression when possible before more complex techniques.
- Document the chosen technique and its impact on complexity for future maintenance.
- Test with randomized inputs and verify results match the original DP.
Example Use Cases
- Convex Hull Trick for a DP with a linear cost and minimum over previous states, reducing from O(n^2) to near O(n log n).
- Divide & Conquer optimization for DP with monotone opt across partitions, improving from O(n^2) to O(n log n) or O(n).
- Knuth optimization for interval DP where the optimal split is monotone, cutting cubic time to quadratic.
- Monotonic Queue for sliding window DP to drop from O(nk) to O(n).
- Bitmask Compression to shrink multi-dimensional DP state space when n is small but states explode.
Frequently Asked Questions
Add this skill to your agents
