dp-pattern-library

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
2. Analyze problem statement for DP indicators
3. Match to known pattern categories
4. Identify problem variants and transformations
5. Suggest state representation

1. Pattern Categories
2. Linear DP (1D array)
3. Grid/Matrix DP (2D paths)
4. String DP (LCS, edit distance)
5. Interval DP (ranges, parenthesization)
6. Tree DP (subtree problems)
7. Bitmask DP (subset enumeration)
8. Digit DP (number counting)
9. Knapsack variants
10. DP with state machine

1. Code Generation
2. Template code for recognized patterns
3. Multiple language support (Python, C++, Java)
4. Comments explaining state and transitions
5. Space-optimized variants

1. Optimization Guidance
2. Rolling array technique
3. Convex hull trick
4. Divide and conquer optimization
5. Monotonic queue/stack optimization
6. Knuth optimization

Pattern Library

Linear DP Patterns

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

String DP Patterns

| Pattern | State | Example Problems | |---------|-------|------------------| | Edit Distance | dp[i][j] = distance for s1[0..i], s2[0..j] | Edit Distance, One Edit Distance | | LCS | dp[i][j] = LCS of s1[0..i], s2[0..j] | Longest Common Subsequence | | Palindrome | dp[i][j] = is s[i..j] palindrome | Longest Palindromic Substring | | Regex Match | dp[i][j] = s[0..i] matches p[0..j] | Regular Expression Matching |

Knapsack Patterns

| Variant | State | Transition | |---------|-------|------------| | 0/1 Knapsack | dp[i][w] = max value with items 0..i, capacity w | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]) | | Unbounded | dp[w] = max value with capacity w | dp[w] = max(dp[w], dp[w-wt[i]] + val[i]) | | Bounded | dp[i][w] = max value with limited items | Use binary representation or deque | | Subset Sum | dp[i][s] = can reach sum s with items 0..i | dp[i][s] = dp[i-1][s] or dp[i-1][s-a[i]] |

Grid DP Patterns

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

Interval DP Patterns

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

Tree DP Patterns

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

Bitmask DP Patterns

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

Usage

Pattern Matching

# 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

# 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

# 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

{
  "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