Master DP patterns with complete implementations for memoization, tabulation, and state design with production-ready solutions.
Provides complete DP implementations for memoization, tabulation, and state design patterns including knapsack, LCS, coin change, and LIS. Use when solving optimization problems requiring recursive state relationships with optimal time-space complexity.
/plugin marketplace add pluginagentmarketplace/custom-plugin-data-structures-algorithms/plugin install data-structures-algorithms-assistant@pluginagentmarketplace-data-structures-algorithmsThis skill inherits all available tools. When active, it can use any tool Claude has access to.
assets/dp_config.yamlreferences/DP_GUIDE.mdscripts/dp_patterns.pyAtomic Responsibility: Execute DP patterns with optimal time-space complexity.
1. Define state: dp[i] = "what does this represent?"
2. Find recurrence: dp[i] = f(dp[i-1], dp[i-2], ...)
3. Identify base cases: dp[0] = ?, dp[1] = ?
4. Determine order: smaller → larger
5. Optimize space: O(n) → O(1) when possible
from typing import List, Dict
from functools import lru_cache
# Memoization (Top-Down)
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
"""
Fibonacci with memoization.
Time: O(n), Space: O(n)
"""
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
# Tabulation (Bottom-Up)
def fib_tabulation(n: int) -> int:
"""
Fibonacci with tabulation.
Time: O(n), Space: O(n)
"""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Space-Optimized
def fib_optimized(n: int) -> int:
"""
Fibonacci with O(1) space.
Time: O(n), Space: O(1)
"""
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1
def knapsack(weights: List[int], values: List[int], capacity: int) -> int:
"""
Classic 0/1 Knapsack problem.
State: dp[i][w] = max value using items 0..i-1 with capacity w
Time: O(n*W), Space: O(n*W)
Args:
weights: Weight of each item
values: Value of each item
capacity: Maximum weight capacity
Returns:
Maximum achievable value
"""
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# Don't take item i-1
dp[i][w] = dp[i - 1][w]
# Take item i-1 if possible
if weights[i - 1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]
)
return dp[n][capacity]
def knapsack_optimized(weights: List[int], values: List[int], capacity: int) -> int:
"""
Space-optimized knapsack using 1D array.
Time: O(n*W), Space: O(W)
Key insight: Iterate capacity in reverse to avoid overwriting.
"""
dp = [0] * (capacity + 1)
for i in range(len(weights)):
# Reverse order to ensure each item used at most once
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
def lcs(text1: str, text2: str) -> int:
"""
Find length of longest common subsequence.
State: dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1]
Time: O(m*n), Space: O(m*n)
"""
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
def lcs_optimized(text1: str, text2: str) -> int:
"""
Space-optimized LCS using two rows.
Time: O(m*n), Space: O(min(m,n))
"""
# Ensure text2 is shorter for space optimization
if len(text1) < len(text2):
text1, text2 = text2, text1
m, n = len(text1), len(text2)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
curr[j] = prev[j - 1] + 1
else:
curr[j] = max(prev[j], curr[j - 1])
prev = curr
return prev[n]
def coin_change(coins: List[int], amount: int) -> int:
"""
Minimum coins to make amount.
State: dp[i] = minimum coins for amount i
Recurrence: dp[i] = min(dp[i], dp[i-coin] + 1)
Time: O(n*amount), Space: O(amount)
Returns:
Minimum coins, or -1 if impossible
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Base case: 0 coins for amount 0
for coin in coins:
for i in range(coin, amount + 1):
if dp[i - coin] != float('inf'):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
def coin_change_ways(coins: List[int], amount: int) -> int:
"""
Count number of ways to make amount.
Note: Order of loops matters!
- Coins outer: combinations (unique ways)
- Amount outer: permutations (order matters)
Time: O(n*amount), Space: O(amount)
"""
dp = [0] * (amount + 1)
dp[0] = 1 # One way to make amount 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
def lis_dp(nums: List[int]) -> int:
"""
Find length of LIS using DP.
State: dp[i] = length of LIS ending at index i
Time: O(n²), Space: O(n)
"""
if not nums:
return 0
n = len(nums)
dp = [1] * n # Each element is LIS of length 1
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)
def lis_binary_search(nums: List[int]) -> int:
"""
Find length of LIS using binary search.
Time: O(n log n), Space: O(n)
Key insight: Maintain smallest tail of LIS for each length.
"""
from bisect import bisect_left
if not nums:
return 0
tails = [] # tails[i] = smallest tail of LIS with length i+1
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
import pytest
class TestDynamicProgramming:
"""Unit tests for DP implementations."""
def test_fibonacci(self):
assert fib_optimized(0) == 0
assert fib_optimized(1) == 1
assert fib_optimized(10) == 55
def test_knapsack(self):
weights = [1, 2, 3]
values = [10, 15, 40]
assert knapsack_optimized(weights, values, 6) == 65
def test_lcs(self):
assert lcs("abcde", "ace") == 3
assert lcs("abc", "def") == 0
def test_coin_change(self):
assert coin_change([1, 2, 5], 11) == 3
assert coin_change([2], 3) == -1
def test_coin_change_ways(self):
assert coin_change_ways([1, 2, 5], 5) == 4
def test_lis(self):
assert lis_binary_search([10, 9, 2, 5, 3, 7, 101, 18]) == 4
| Issue | Cause | Solution |
|---|---|---|
| Wrong answer | Incorrect recurrence | Verify with small examples |
| Stack overflow | Deep memoization | Use tabulation instead |
| TLE | Missing memoization | Add @lru_cache or explicit memo |
| MLE | Full 2D table | Apply space optimization |
□ State definition clear and complete?
□ Recurrence handles all cases?
□ Base cases cover edge inputs?
□ Computation order respects dependencies?
□ Return value correct (dp[n] vs dp[n-1])?
□ Space optimization maintains correctness?
This skill should be used when the user asks to "create a slash command", "add a command", "write a custom command", "define command arguments", "use command frontmatter", "organize commands", "create command with file references", "interactive command", "use AskUserQuestion in command", or needs guidance on slash command structure, YAML frontmatter fields, dynamic arguments, bash execution in commands, user interaction patterns, or command development best practices for Claude Code.
This skill should be used when the user asks to "create an agent", "add an agent", "write a subagent", "agent frontmatter", "when to use description", "agent examples", "agent tools", "agent colors", "autonomous agent", or needs guidance on agent structure, system prompts, triggering conditions, or agent development best practices for Claude Code plugins.
This skill should be used when the user asks to "create a hook", "add a PreToolUse/PostToolUse/Stop hook", "validate tool use", "implement prompt-based hooks", "use ${CLAUDE_PLUGIN_ROOT}", "set up event-driven automation", "block dangerous commands", or mentions hook events (PreToolUse, PostToolUse, Stop, SubagentStop, SessionStart, SessionEnd, UserPromptSubmit, PreCompact, Notification). Provides comprehensive guidance for creating and implementing Claude Code plugin hooks with focus on advanced prompt-based hooks API.