Use when solving optimization problems with overlapping subproblems and optimal substructure. Covers memoization (top-down) vs tabulation (bottom-up), classic DP problems (Knapsack, LCS, LIS, Edit Distance, Coin Change, Matrix Chain, Rod Cutting), and the DP framework. Based on Knuth's TAOCP.
USE FOR: optimization problems with overlapping subproblems, memoization strategies, tabulation approaches, recognizing DP problem patterns, state definition and recurrence formulation
DO NOT USE FOR: graph shortest paths (use graph-algorithms), sorting (use sorting-searching)
Instalar com Codex ou Claude Copie este prompt, cole no Codex, Claude ou outro assistente e deixe que ele revise a página da skill e instale para você.
Um comando direto ignora o prompt de revisão. Verifique a origem antes de executá-lo.
Use when solving optimization problems with overlapping subproblems and optimal substructure. Covers memoization (top-down) vs tabulation (bottom-up), classic DP problems (Knapsack, LCS, LIS, Edit Distance, Coin Change, Matrix Chain, Rod Cutting), and the DP framework. Based on Knuth's TAOCP.
USE FOR: optimization problems with overlapping subproblems, memoization strategies, tabulation approaches, recognizing DP problem patterns, state definition and recurrence formulation
DO NOT USE FOR: graph shortest paths (use graph-algorithms), sorting (use sorting-searching)
[{"title":"The Art of Computer Programming — Donald Knuth","url":"https://www-cs-faculty.stanford.edu/~knuth/taocp.html"},{"title":"Dynamic Programming — Wikipedia","url":"https://en.wikipedia.org/wiki/Dynamic_programming"}]
Dynamic Programming
Overview
Dynamic programming (DP) is a method for solving problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results to avoid redundant computation. Knuth discusses dynamic programming techniques throughout , particularly in the context of optimization, sequence analysis, and combinatorial problems. The term was coined by Richard Bellman in the 1950s.
The Art of Computer Programming
Core Principles
Optimal Substructure
A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems. This property allows us to build the global optimum from local optima.
Example: The shortest path from A to C through B consists of the shortest path from A to B plus the shortest path from B to C.
Overlapping Subproblems
A problem has overlapping subproblems when the same subproblems are solved repeatedly in a naive recursive approach. DP eliminates this redundancy by storing results.
Example: Computing Fibonacci(n) recursively recomputes Fibonacci(k) for each k < n exponentially many times.
Two Approaches
Memoization (Top-Down)
Start with the original problem, recurse into subproblems, and cache results as they are computed.
FIB_MEMO(n, cache):
if n <= 1: return n
if n in cache: return cache[n]
cache[n] = FIB_MEMO(n - 1, cache) + FIB_MEMO(n - 2, cache)
return cache[n]
Advantages: Natural to write (follows recursive structure), computes only the subproblems actually needed.
Disadvantages: Recursion overhead, potential stack overflow for deep recursion.
Tabulation (Bottom-Up)
Build a table from the smallest subproblems up to the desired result, iterating in a careful order.
FIB_TABLE(n):
if n <= 1: return n
dp[0] = 0, dp[1] = 1
for i = 2 to n:
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
Advantages: No recursion overhead, easier to optimize space (often only need the last few entries).
Disadvantages: May compute subproblems that are never needed, ordering can be less intuitive.
The DP Framework
When facing a potential DP problem, follow these steps:
1. Define the State
Identify what information is needed to describe a subproblem. This becomes the index/key for your DP table.
Example (Knapsack): dp[i][w] = maximum value using items 1..i with capacity w.
2. Write the Recurrence
Express the solution to a subproblem in terms of smaller subproblems.
Example (Knapsack):
dp[i][w] = max(
dp[i-1][w], // skip item i
dp[i-1][w - weight[i]] + value[i] // take item i (if weight[i] <= w)
)
3. Identify the Base Case
Define the values for the smallest subproblems that cannot be decomposed further.
Example (Knapsack): dp[0][w] = 0 for all w (no items means no value).
4. Determine the Build Order
For tabulation, compute subproblems in an order such that all dependencies are resolved before they are needed.
Example (Knapsack): Process items from i = 1 to n, capacities from w = 0 to W.
5. Extract the Answer
The answer to the original problem is at a specific location in the DP table.
Example (Knapsack): dp[n][W].
6. (Optional) Optimize Space
If the recurrence only depends on the previous row or a fixed number of prior entries, reduce the table accordingly.
Example (Fibonacci): Only need dp[i-1] and dp[i-2], so use two variables instead of an array.
Classic Problems
Fibonacci Sequence
Approach
Time
Space
Naive recursion
O(2^n)
O(n) stack
Memoization
O(n)
O(n)
Tabulation
O(n)
O(n) or O(1) optimized
0/1 Knapsack
Given n items with weights and values, and a knapsack of capacity W, maximize the total value without exceeding the capacity. Each item can be taken at most once.
State: dp[i][w] = max value using first i items with capacity w
