Overview

Assists in designing optimal dynamic programming states, transitions, and optimizations for complex problems. It helps identify subproblem structure, choose state parameters, derive transitions, and spot memory-saving tricks like rolling arrays or bitmasks.

How This Skill Works

By analyzing the problem description and constraints, it identifies subproblems, proposes state definitions (dimensions and parameters), derives transition formulas, and lists base cases and computation order. It also surfaces optimization opportunities and outputs a structured design that can be implemented directly.

When to Use It

• You have a DP problem with unclear or large state space and need a systematic way to define state parameters.
• You want to derive clean transition formulas and ensure all subproblems are covered without duplicates.
• You seek memory or time optimizations (e.g., rolling arrays, bitmask compression) and want to quantify potential gains.
• You need a reproducible design framework to verify base cases and computation order.
• You want to compare multiple DP design options (state definitions vs. transitions) for a given problem.

Quick Start

1. Step 1: Provide problemDescription and requestType (fullDesign, stateOnly, transitions, optimize).
2. Step 2: Identify subproblems and draft initial state definitions (parameters and dimensions).
3. Step 3: Derive transitions, specify base cases and computation order, then note any space/time optimizations.

Best Practices

• Start with Subproblem Identification: break the problem into smaller, overlapping subproblems.
• Define Minimal State: choose state parameters that uniquely identify subproblems with the smallest necessary dimensionality.
• Derive Clear Transitions: express how subproblem solutions combine to form larger problems.
• Pin Base Cases and Order: specify trivial subproblems and a feasible computation order for DP.
• Validate with Optimizations: assess potential space/time optimizations and verify correctness against constraints.

Example Use Cases

• Knapsack with rolling array optimization to reduce space from O(nW) to O(W).
• Longest Common Subsequence by clearly defining indices as state dimensions.
• Edit Distance via transitions on character operations and base cases for empty strings.
• Subset Sum using bitmask compression to represent reachable sums.
• Grid path counting by defining position and step count as state parameters.

Frequently Asked Questions