Standardmäßig ist der Prompt ausgewählt, der zuerst die Quelle prüft. Sie können zu einem direkten Befehl wechseln oder eine lokale Kopie herunterladen.
Quelldateien prüfen
Lesen Sie SKILL.md und alle von SkillsMP angezeigten Begleitdateien, bevor Sie sich für eine Installation entscheiden.
Mit Codex oder Claude installieren Kopieren Sie diesen Prompt, fügen Sie ihn in Codex, Claude oder einen anderen Assistant ein und lassen Sie die Skill-Seite prüfen und installieren.
Ein direkter Befehl überspringt den Prüf-Prompt. Prüfen Sie die Quelle, bevor Sie ihn ausführen.
Atomic Responsibility: Execute DP patterns with optimal time-space complexity.
DP Framework
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
Fibonacci Pattern
from typing importList, Dictfrom functools import lru_cache
# Memoization (Top-Down)@lru_cache(maxsize=None)deffib_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)deffib_tabulation(n: int) -> int:
"""
Fibonacci with tabulation.
Time: O(n), Space: O(n)
"""if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1for i inrange(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
dp[n]
() -> :
n <= :
n
prev2, prev1 = ,
_ (, n + ):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
prev1
return
# Space-Optimized
def
fib_optimized
n: int
int
"""
Fibonacci with O(1) space.
Time: O(n), Space: O(1)
"""
if
1
return
0
1
for
in
range
2
1
return
0/1 Knapsack Pattern
defknapsack(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 _ inrange(n + 1)]
for i inrange(1, n + 1):
for w inrange(capacity + 1):
# Don't take item i-1
dp[i][w] = dp[i - 1][w]
# Take item i-1 if possibleif 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]
defknapsack_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 inrange(len(weights)):
# Reverse order to ensure each item used at most oncefor w inrange(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
Longest Common Subsequence (LCS)
deflcs(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 _ inrange(m + 1)]
for i inrange(1, m + 1):
for j inrange(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
deflcs_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 optimizationiflen(text1) < len(text2):
text1, text2 = text2, text1
m, n = len(text1), len(text2)
prev = [0] * (n + 1)
for i inrange(1, m + 1):
curr = [0] * (n + 1)
for j inrange(1, n + 1):
if text1[i - 1] == text2[j - 1]:
curr[j] = prev[j - 1] + 1else:
curr[j] = max(prev[j], curr[j - 1])
prev = curr
return prev[n]
Coin Change Pattern
defcoin_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 0for coin in coins:
for i inrange(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 -1defcoin_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 0for coin in coins:
for i inrange(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
Longest Increasing Subsequence (LIS)
deflis_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)
"""ifnot nums:
return0
n = len(nums)
dp = [1] * n # Each element is LIS of length 1for i inrange(1, n):
for j inrange(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
returnmax(dp)
deflis_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
ifnot nums:
return0
tails = [] # tails[i] = smallest tail of LIS with length i+1for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
returnlen(tails)
□ 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?
