dp-pattern-library

A specialized skill for dynamic programming pattern recognition, matching problems to known DP patterns, generating template code, and providing optimization guidance for DP solutions.

Purpose

Assist with dynamic programming by:

• Matching problems to 50+ classic DP patterns
• Generating template code for matched patterns
• Detecting problem variants (knapsack variants, LCS variants, etc.)
• Providing state design recommendations
• Suggesting optimization techniques

Capabilities

Core Features

1. Pattern Recognition

• Analyze problem statement for DP indicators
• Match to known pattern categories
• Identify problem variants and transformations
• Suggest state representation

1. Pattern Categories

• Linear DP (1D array)
• Grid/Matrix DP (2D paths)
• String DP (LCS, edit distance)
• Interval DP (ranges, parenthesization)
• Tree DP (subtree problems)
• Bitmask DP (subset enumeration)
• Digit DP (number counting)
• Knapsack variants
• DP with state machine

1. Code Generation

• Template code for recognized patterns
• Multiple language support (Python, C++, Java)
• Comments explaining state and transitions
• Space-optimized variants

1. Optimization Guidance

• Rolling array technique
• Convex hull trick
• Divide and conquer optimization
• Monotonic queue/stack optimization
• Knuth optimization

Pattern Library

Linear DP Patterns

| Pattern | State | Transition | Example Problems | |---------|-------|------------|------------------| | Fibonacci | dpi] = answer for position i | dpi] = dpi-1] + dpi-2] | Climbing Stairs, House Robber | | Min/Max Path | dpi] = best answer ending at i | dpi] = opt(dpj]) + cost(j,i) | Minimum Path Sum | | Counting | dpi] = ways to reach state i | dpi] = sum(dpj]) | Unique Paths, Decode Ways | | LIS | dpi] = LIS ending at i | dpi] = max(dpj]) + 1 where j < i, aj] < ai] | Longest Increasing Subsequence |

String DP Patterns

| Pattern | State | Example Problems | |---------|-------|------------------| | Edit Distance | dpi]j] = distance for s10..i], s20..j] | Edit Distance, One Edit Distance | | LCS | dpi]j] = LCS of s10..i], s20..j] | Longest Common Subsequence | | Palindrome | dpi]j] = is si..j] palindrome | Longest Palindromic Substring | | Regex Match | dpi]j] = s0..i] matches p0..j] | Regular Expression Matching |

Knapsack Patterns

| Variant | State | Transition | |---------|-------|------------| | 0/1 Knapsack | dpi]w] = max value with items 0..i, capacity w | dpi]w] = max(dpi-1]w], dpi-1]w-wti]] + vali]) | | Unbounded | dpw] = max value with capacity w | dpw] = max(dpw], dpw-wti]] + vali]) | | Bounded | dpi]w] = max value with limited items | Use binary representation or deque | | Subset Sum | dpi]s] = can reach sum s with items 0..i | dpi]s] = dpi-1]s] or dpi-1]s-ai]] |

Grid DP Patterns

| Pattern | State | Example Problems | |---------|-------|------------------| | Path Count | dpi]j] = ways to reach (i,j) | Unique Paths, Unique Paths II | | Path Min/Max | dpi]j] = best path to (i,j) | Minimum Path Sum | | Multi-path | dpi]j]k]l] = two paths simultaneously | Cherry Pickup |

Interval DP Patterns

| Pattern | State | Example Problems | |---------|-------|------------------| | MCM | dpi]j] = cost for range i,j] | Matrix Chain Multiplication | | Burst | dpi]j] = max coins from balloonsi..j] | Burst Balloons | | Merge | dpi]j] = cost to merge range i,j] | Minimum Cost to Merge Stones |

Tree DP Patterns

| Pattern | State | Example Problems | |---------|-------|------------------| | Subtree | dpv] = answer for subtree rooted at v | Binary Tree Maximum Path Sum | | Rerooting | dpv] = answer when v is root | Sum of Distances in Tree | | Parent-Child | dpv]0/1] = answer with constraint | House Robber III |

Bitmask DP Patterns

| Pattern | State | Example Problems | |---------|-------|------------------| | TSP | dpmask]last] = min cost visiting mask cities ending at last | Traveling Salesman Problem | | Assignment | dpmask] = min cost assigning tasks to subset | Task Assignment | | SOS | dpmask] = sum over subsets | Subset Sum over Subsets |

Usage

Pattern Matching

bash
# Match problem to DP pattern
dp-pattern-library match --problem "Given an array of integers, find the longest increasing subsequence"

# Output:
# Pattern: Linear DP - Longest Increasing Subsequence (LIS)
# State: dp[i] = length of LIS ending at index i
# Transition: dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
# Time: O(n^2) naive, O(n log n) with binary search
# Space: O(n)

Template Generation

bash
# Generate template code
dp-pattern-library template --pattern "lis" --language python

# Output:
def lengthOfLIS(nums):
    if not nums:
        return 0

    n = len(nums)
    # dp[i] = length of LIS ending at index i
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Optimization Suggestions

bash
# Get optimization recommendations
dp-pattern-library optimize --pattern "lis"

# Output:
# Current: O(n^2) time, O(n) space
# Optimizations:
# 1. Binary Search: O(n log n) time
#    - Maintain sorted list of smallest tail elements
#    - Binary search for insertion point
# 2. Segment Tree: O(n log n) time
#    - For coordinate compression + range max query

Output Schema

json
{
  "match": {
    "pattern": "Linear DP - LIS",
    "confidence": 0.95,
    "category": "linear",
    "variants": ["LIS", "LDS", "LNDS"]
  },
  "state": {
    "description": "dp[i] = length of LIS ending at index i",
    "dimensions": 1,
    "meaning": "LIS length ending at position i"
  },
  "transition": {
    "formula": "dp[i] = max(dp[j] + 1) for j < i, arr[j] < arr[i]",
    "baseCase": "dp[i] = 1 for all i",
    "order": "left to right"
  },
  "complexity": {
    "time": "O(n^2)",
    "space": "O(n)",
    "optimized": {
      "time": "O(n log n)",
      "technique": "binary search on patience sort"
    }
  },
  "template": {
    "python": "...",
    "cpp": "...",
    "java": "..."
  },
  "similarProblems": [
    "Longest Increasing Subsequence",
    "Number of Longest Increasing Subsequence",
    "Russian Doll Envelopes",
    "Maximum Length of Pair Chain"
  ]
}

Integration with Processes

This skill enhances:

• dp-pattern-matching - Core pattern matching workflow
• dp-state-optimization - State space optimization
• dp-transition-derivation - Deriving transitions
• leetcode-problem-solving - DP problem identification
• classic-dp-library - Building a personal DP library

Pattern Recognition Indicators

| Indicator | Likely Pattern | |-----------|----------------| | "maximum/minimum" + "subarray/subsequence" | Linear DP | | "number of ways" | Counting DP | | "can reach/achieve" | Boolean DP | | "edit/transform string" | String DP | | "merge/combine intervals" | Interval DP | | "tree/subtree" | Tree DP | | "select subset" + small n | Bitmask DP | | "count numbers with property" | Digit DP | | "items + capacity" | Knapsack |

References

• Dynamic Programming Patterns
• DP Visualization Tools
• LeetCode DP Patterns
• CP Algorithms - DP
• CSES DP Section

Error Handling

| Error | Cause | Resolution | |-------|-------|------------| | NO_PATTERN_MATCH | Problem doesn't fit known patterns | Consider greedy or other approaches | | AMBIGUOUS_MATCH | Multiple patterns could apply | Provide more problem details | | COMPLEX_STATE | State too complex for templates | Manual state design needed |

Best Practices

1. Start with brute force - Understand recurrence before optimizing
2. Draw state diagram - Visualize transitions
3. Verify base cases - Most DP bugs are in base cases
4. Check state uniqueness - Each state should be uniquely defined
5. Consider space optimization - Often can reduce dimension
6. Test with small inputs - Trace through by hand