Loading learning content...
If you ask any seasoned competitive programmer or principal engineer what separates those who struggle with dynamic programming from those who solve DP problems effortlessly, you'll hear the same answer: the ability to define state precisely.
State design is not a minor implementation detail—it is the essence of dynamic programming. Get the state right, and the recurrence relation often writes itself. Get it wrong, and no amount of clever coding will save you. You'll either solve the wrong problem entirely, or find yourself in an infinite recursion with no clear path forward.
By the end of this page, you will understand what DP state truly means, how to think about state as a complete description of 'where you are' in a problem, how to choose state dimensions that capture exactly the right information, and how to analyze state space size to predict algorithm efficiency. You'll develop the mental framework that makes DP problems feel systematic rather than magical.
Let's begin with the most fundamental question: What exactly is a DP state?
A DP state is a compact representation of all information needed to compute the optimal solution for a subproblem. Think of it as a snapshot of your progress through the problem that captures everything you need to know to continue, while discarding everything you don't.
Consider an analogy: Imagine you're playing a complex video game and need to save your progress. The game's save file doesn't record every single action you took—it records the state of the game: your position, inventory, health, quest progress, and other relevant metrics. From this state, the game can continue perfectly, even though it has 'forgotten' the specific sequence of actions that led there.
DP states exhibit what mathematicians call the Markov property: the future depends only on the current state, not on how you arrived at that state. If two different paths through a problem lead to the same state, their futures are identical. This is why DP works—we can solve each unique state once and reuse the result, regardless of how we reached it.
Formal Definition:
A DP state is a tuple of values (x₁, x₂, ..., xₖ) such that:
Completeness: From this tuple, you can compute the optimal solution to the corresponding subproblem without any additional information about the problem's history.
Distinctiveness: Different tuples represent genuinely different subproblems—no two distinct states have the same optimal answer under all inputs.
Finiteness: The total number of possible state tuples is finite (or at least bounded in a way that makes computation tractable).
Let's see what this means with a concrete example.
n = 1055The state is simply the index n. To compute F(n), we only need to know n—not how we 'got' to wanting F(n). The state tuple is just (n), a 1-dimensional state. The state space has n+1 states: F(0), F(1), F(2), ..., F(n).
But problems quickly get more interesting. Consider the classic Climbing Stairs problem with a twist: you can climb 1, 2, or 3 steps, but cannot use the same step size twice consecutively. Now our state needs to capture not just where we are, but also how we got there (at least partially).
The state becomes (current_stair, last_step_size). From this tuple, we know everything needed to enumerate valid next moves. We've captured the essential 'history' without recording every step taken.
Selecting the right state is both science and art. Too little information in your state, and you can't solve the subproblems correctly. Too much information, and your state space explodes, making the algorithm impractical.
The Golden Rule: Include in your state exactly the information that:
And exclude everything else.
A frequent mistake is including information in the state that doesn't actually affect the problem. For the 0/1 Knapsack problem, you don't need to track which specific items you've taken—only the total weight used and how many items you've considered. The 'which items' detail is reconstruction information, not state-defining information.
Systematic State Selection Process:
When facing a new DP problem, ask yourself these questions in order:
Question 1: What changes as I make decisions?
Question 2: What constraints must I respect?
Question 3: What's the minimal set of variables that capture the above?
| Problem | Naive State Attempt | Optimal State | Why Optimal Works |
|---|---|---|---|
| 0/1 Knapsack | (items_taken_set, weight) | (i, weight) | Order of consideration doesn't matter—only which items we've had the chance to take |
| Longest Common Subsequence | (chars_matched_so_far, pos_in_A, pos_in_B) | (i, j) | The matched characters are determined by i, j—we only need endpoints |
| Edit Distance | (edit_sequence, pos_A, pos_B) | (i, j) | The sequence of edits is reconstructable; positions define the subproblem |
| Coin Change | (coins_used_list, remaining) | (remaining) | For minimum count, which coins used doesn't affect future—only remaining amount |
| House Robber | (houses_robbed_set, current_house) | (i, prev_robbed) | Only whether we robbed the previous house affects current choice |
The dimensionality of a DP state refers to how many independent pieces of information the state contains. This directly determines the size of your DP table and, consequently, your algorithm's time and space complexity.
1D State (Single Variable):
dp[i] where i is a single index or value123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
# ===== 1D STATE: Coin Change =====# State: dp[amount] = minimum coins to make 'amount'# Only one dimension: the target amount def coin_change_1d(coins: list[int], amount: int) -> int: """ State Definition: dp[a] = minimum number of coins needed to make amount 'a' Why 1D is sufficient: - The subproblem is fully defined by the remaining amount - We don't care WHICH coins were used before, only the remaining target - Each amount from 0 to 'amount' is a unique subproblem """ # Initialize state space: amount + 1 states (0 through amount) dp = [float('inf')] * (amount + 1) dp[0] = 0 # Base case: 0 coins needed for amount 0 for a in range(1, amount + 1): for coin in coins: if coin <= a and dp[a - coin] != float('inf'): dp[a] = min(dp[a], dp[a - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 # ===== 1D STATE: House Robber (simplified) =====# Note: This uses O(n) space; see space optimization for O(1)def house_robber(nums: list[int]) -> int: """ State Definition: dp[i] = maximum money obtainable considering houses 0..i Why 1D works: - Each house decision only depends on whether we robbed i-1 - We track "best up to here" which encapsulates all prior decisions """ if not nums: return 0 if len(nums) == 1: return nums[0] n = len(nums) dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i-1], dp[i-2] + nums[i]) return dp[n-1]2D State (Two Variables):
dp[i][j] where i and j are independent indices123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
# ===== 2D STATE: Longest Common Subsequence =====# State: dp[i][j] = LCS length of A[0..i-1] and B[0..j-1]# Two dimensions: position in string A, position in string B def lcs_length(A: str, B: str) -> int: """ State Definition: dp[i][j] = length of LCS of A[0..i-1] and B[0..j-1] Why 2D is necessary: - We need to know how far we've processed in BOTH strings - The subproblem "LCS of first i chars of A and first j chars of B" is uniquely determined by the pair (i, j) - Neither i nor j alone captures the full subproblem State Space Analysis: - i ranges from 0 to len(A): that's (len(A) + 1) values - j ranges from 0 to len(B): that's (len(B) + 1) values - Total states: (len(A) + 1) × (len(B) + 1) = O(n × m) """ m, n = len(A), len(B) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if A[i-1] == B[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] # ===== 2D STATE: 0/1 Knapsack =====# State: dp[i][w] = max value using items 0..i-1 with capacity w# Two dimensions: item index, remaining capacity def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int: """ State Definition: dp[i][w] = maximum value achievable using items 0..i-1 with knapsack capacity w Why 2D is necessary: - We must track which items we've "considered" (index i) - We must track remaining capacity (w) - Both pieces of information affect valid transitions State Space: O(n × W) where n = items, W = capacity """ 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 it fits) 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]3D+ State (Three or More Variables):
dp[i][j][k] or higher dimensions123456789101112131415161718192021222324252627282930313233343536373839404142434445
# ===== 3D STATE: Best Time to Buy and Sell Stock with Cooldown =====# State: dp[i][j][k] where i = day, j = holding stock?, k = cooldown remaining # A cleaner formulation uses 3 separate arrays, but conceptually it's 3D def max_profit_cooldown(prices: list[int]) -> int: """ State Definition (Conceptual 3D): dp[i][holding][cooldown] = max profit at day i Simplified State (equivalent): hold[i] = max profit at day i if we ARE holding stock sold[i] = max profit at day i if we JUST sold (in cooldown) rest[i] = max profit at day i if we are NOT holding and NOT in cooldown Why 3 states are needed: - 'holding' affects what actions are legal (can only sell if holding) - 'cooldown' affects what actions are legal (can't buy during cooldown) - The day 'i' marks progression through the problem State Space: O(n × 2 × 2) = O(4n) = O(n) states """ if not prices or len(prices) < 2: return 0 n = len(prices) # hold[i]: max profit ending day i while holding stock # sold[i]: max profit ending day i having just sold (entering cooldown) # rest[i]: max profit ending day i without stock and not in cooldown hold = [0] * n sold = [0] * n rest = [0] * n hold[0] = -prices[0] # Bought on day 0 sold[0] = 0 # Can't sell on day 0 (nothing to sell) rest[0] = 0 # Did nothing on day 0 for i in range(1, n): hold[i] = max(hold[i-1], rest[i-1] - prices[i]) # Keep or buy sold[i] = hold[i-1] + prices[i] # Sell rest[i] = max(rest[i-1], sold[i-1]) # Do nothing return max(sold[n-1], rest[n-1]) # Must not be holding at the endEach independent constraint or sequence in your problem typically adds one dimension to your state. Two strings → 2D. One sequence with a constraint → 2D. Grid with limited resources → 3D. If your state seems to need 4+ dimensions, look for ways to encode multiple constraints together or reconsider whether DP is the right approach.
Before implementing any DP solution, you must analyze your state space—the total number of distinct states your solution will compute. This analysis tells you:
Time Complexity: At minimum, you must visit each state once. If each state takes O(T) time to compute from its dependencies, total time is O(states × T).
Space Complexity: In the naive case, you store a value for each state. Space equals O(states), though optimization can often reduce this.
Feasibility: If your state space is too large (say, 10¹⁵ states), the approach is impractical regardless of how clever your implementation is.
| Problem | State Variables | State Space Size | Time Complexity | Space Complexity |
|---|---|---|---|---|
| Fibonacci | n | O(n) | O(n) | O(n) → O(1) |
| Coin Change | amount | O(amount) | O(amount × coins) | O(amount) |
| LCS | (i, j) | O(n × m) | O(n × m) | O(n × m) → O(min(n,m)) |
| Edit Distance | (i, j) | O(n × m) | O(n × m) | O(n × m) → O(min(n,m)) |
| 0/1 Knapsack | (i, w) | O(n × W) | O(n × W) | O(n × W) → O(W) |
| Matrix Chain | (i, j) | O(n²) | O(n³) | O(n²) |
| TSP Bitmask | (mask, last) | O(2ⁿ × n) | O(2ⁿ × n²) | O(2ⁿ × n) |
Performing State Space Analysis:
For each state variable, determine its range:
State: (i, j, k)
- i ranges from 0 to n: (n+1) values
- j ranges from 0 to m: (m+1) values
- k ranges from 0 to K: (K+1) values
Total states: (n+1) × (m+1) × (K+1) ≈ O(n × m × K)
Critical Insight: Not All States May Be Reachable
Sometimes the theoretical state space overestimates the actual number of subproblems. For instance, in a constrained problem, certain state combinations may be impossible. However, for complexity analysis, we typically consider the worst-case state space.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
# ===== STATE SPACE ANALYSIS: Constrained Subset Sum =====# Problem: How many subsets of array sum to exactly K? def count_subset_sums(nums: list[int], K: int) -> int: """ State Analysis: State: (index i, current_sum s) Theoretical space: - i: 0 to n → (n+1) values - s: could be anything from 0 to sum(nums) Actual space complexity: O(n × K) Why? We only care about sums up to K. Any sum > K cannot lead to a solution, so we can prune those states. This is a key insight: the STATE SPACE can be BOUNDED by the problem constraints, not just the input size. """ n = len(nums) # dp[i][s] = number of ways to achieve sum s using first i elements dp = [[0] * (K + 1) for _ in range(n + 1)] dp[0][0] = 1 # One way to make sum 0 with 0 elements: take nothing for i in range(1, n + 1): for s in range(K + 1): # Don't include nums[i-1] dp[i][s] = dp[i-1][s] # Include nums[i-1] if it doesn't exceed target if nums[i-1] <= s: dp[i][s] += dp[i-1][s - nums[i-1]] return dp[n][K] # ===== STATE SPACE ANALYSIS: When States Are Sparse =====# Problem: Minimum jumps to reach end of array def min_jumps_sparse(nums: list[int]) -> int: """ Interesting State Space Observation: If we define state as (position, jumps_made), the theoretical state space is O(n × n) since we might make up to n-1 jumps. But a greedy/BFS approach shows that optimal paths grow the 'reachable' window, so we actually only need O(n) states. This illustrates that some problems have "deceptive" state spaces where the true complexity is lower than a naive state definition would suggest. """ n = len(nums) if n <= 1: return 0 jumps = 0 current_end = 0 # Farthest we can reach with 'jumps' jumps farthest = 0 # Farthest we can reach with 'jumps + 1' jumps for i in range(n - 1): farthest = max(farthest, i + nums[i]) if i == current_end: jumps += 1 current_end = farthest if current_end >= n - 1: break return jumpsTime complexity is O(states × transitions_per_state). A problem with O(n²) states and O(1) transitions per state runs in O(n²). A problem with O(n) states but O(n) transitions per state also runs in O(n²). Both the number of states AND the work per state matter for the final complexity.
While every problem is unique, certain state design patterns appear repeatedly across DP problems. Recognizing these patterns accelerates your problem-solving dramatically.
dp[i], LCS dp[i][j], Grid paths dp[r][c].dp[i][w] (w = remaining capacity), Coin Change dp[amount] (remaining amount).dp[i][robbed_prev], Paint House dp[i][color].dp[i][j], Palindrome Partitioning dp[i][j], Burst Balloons dp[i][j].dp[mask][last], Assign Tasks dp[mask], Set Partition problems.dp[i][j], LCS variants, Sequence alignment.Pattern Recognition Tips:
When you see 'optimal over a subsequence', think index-based state (dp[i] = best answer for first i elements).
When you see 'limited resources' (budget, capacity, time), add a resource dimension.
When you see 'consecutive constraints' (can't repeat same action, must alternate), add a 'last action' dimension.
When you see 'interval operations' (remove from ends, merge adjacent), use interval dp[i][j].
Warning Signs of Wrong State:
Infinite loops in recursion: Your state doesn't properly reduce the problem.
Different paths give different answers for 'same' state: You're missing information—add another dimension.
State space is impossibly large: You're tracking too much—look for what can be dropped.
Base cases seem arbitrary: Your state definition may be unnatural for the problem.
Let's walk through the complete state design process for a moderately complex problem.
Problem: Best Time to Buy and Sell Stock IV
You are given an array prices where prices[i] is the price of a stock on day i. Find the maximum profit you can achieve with at most k transactions. A transaction consists of buying then selling one share of stock. You cannot engage in multiple transactions simultaneously (you must sell before you buy again).
Step 1: Identify What Changes
Step 2: Define State Variables
i: Current day (0 to n-1)j: Number of transactions used so far (0 to k)holding: Whether we hold a stock (0 = no, 1 = yes)State Definition: dp[i][j][holding] = maximum profit at end of day i, having used at most j transactions, with holding status = holding
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
def max_profit_k_transactions(k: int, prices: list[int]) -> int: """ Complete State Design Analysis: STATE DEFINITION: dp[i][j][h] = maximum profit achievable where: - i = day index (0 to n-1) - j = transactions used (0 to k), we count a buy as starting a transaction - h = holding status (0 = not holding, 1 = holding) STATE SPACE: - i: n values (0 to n-1) - j: k+1 values (0 to k) - h: 2 values (0 or 1) Total: O(n × k × 2) = O(n × k) TRANSITIONS (from state dp[i][j][h]): If h = 0 (not holding): - Rest: dp[i+1][j][0] can come from dp[i][j][0] (do nothing) - Buy: dp[i+1][j+1][1] can come from dp[i][j][0] - prices[i] (start new transaction, spend money to buy) If h = 1 (holding): - Rest: dp[i+1][j][1] can come from dp[i][j][1] (keep holding) - Sell: dp[i+1][j][0] can come from dp[i][j][1] + prices[i] (complete transaction by selling) BASE CASES: dp[0][0][0] = 0 (day 0, no transactions, not holding) dp[0][1][1] = -prices[0] (day 0, 1 transaction started, holding) All other dp[0][j][h] = -infinity (impossible states) ANSWER: max(dp[n-1][j][0] for j in 0..k) We want the max profit on last day, not holding, any # transactions """ if not prices or k == 0: return 0 n = len(prices) # Edge case: if k >= n//2, we can make unlimited transactions # Switch to simpler O(n) solution if k >= n // 2: return sum(max(0, prices[i] - prices[i-1]) for i in range(1, n)) # dp[j][h]: on current day, with j transactions used, holding status h # We use 2D instead of 3D by processing days iteratively INF = float('inf') # dp[j][0] = max profit with j transactions, not holding # dp[j][1] = max profit with j transactions, holding dp = [[-INF, -INF] for _ in range(k + 2)] # k+2 to avoid index issues dp[0][0] = 0 # 0 transactions, not holding, profit = 0 for price in prices: # Process in reverse to avoid using updated values in same iteration new_dp = [row[:] for row in dp] # Copy for j in range(k + 1): # If not holding, we can buy (starts transaction j+1) if dp[j][0] != -INF and j < k: new_dp[j + 1][1] = max(new_dp[j + 1][1], dp[j][0] - price) # If holding, we can sell (doesn't change transaction count) if dp[j][1] != -INF: new_dp[j][0] = max(new_dp[j][0], dp[j][1] + price) # Can always rest (do nothing) # new_dp[j][h] = max(new_dp[j][h], dp[j][h]) -- already copied dp = new_dp # Find maximum profit across all transaction counts, not holding return max(dp[j][0] for j in range(k + 1) if dp[j][0] != -INF) # Alternative cleaner implementationdef max_profit_k_clean(k: int, prices: list[int]) -> int: """ Cleaner O(nk) space implementation using intuitive naming. """ if not prices or k == 0: return 0 n = len(prices) if k >= n // 2: return sum(max(0, prices[i] - prices[i-1]) for i in range(1, n)) # buy[j] = max profit after j-th buy # sell[j] = max profit after j-th sell buy = [float('-inf')] * (k + 1) sell = [0] * (k + 1) for price in prices: for j in range(1, k + 1): # j-th buy: either already bought, or buy now after (j-1)th sell buy[j] = max(buy[j], sell[j-1] - price) # j-th sell: either already sold, or sell now after j-th buy sell[j] = max(sell[j], buy[j] + price) return sell[k]Always verify your state design by asking: (1) Does every valid problem configuration map to exactly one state? (2) Is the state space finite and tractable? (3) Can I write transitions from any valid state? (4) Are my base cases well-defined? If yes to all, your state design is correct.
We've covered the foundational skill of DP state design. Let's consolidate the key insights:
What's Next:
With the ability to define state precisely, we can now ask: What information should each state track? The next page dives into the art of deciding what to include in your state—balancing completeness against tractability, and handling the subtle cases where the 'obvious' state is insufficient.
You now understand DP state as a complete, minimal representation of subproblems. You can analyze state dimensionality and space, recognize common patterns, and verify your state design. Next, we'll explore what specific information to track within states for different problem types.