Installer avec Codex ou Claude Copiez ce prompt, collez-le dans Codex, Claude ou un autre assistant, puis laissez-le vérifier la page du skill et l'installer pour vous.
Une commande directe contourne le prompt de vérification. Examinez la source avant de l'exécuter.
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?
