Defining DP State… — State Design & Transition… | OneNoughtOne

0/97

Data Structures & AlgorithmsState Design & Transition Functions

State Design & Transition Functions

LevelAdvanced

Duration90 mins

TopicState Design & Transition Functions

1 / 4

Defining DP State Precisely

The Heart of Dynamic Programming

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.

What You Will Learn

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.

What Is DP State?

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.

The Markov Property

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.

Fibonacci: The Simplest State

Consider computing the n-th Fibonacci number.

Input

n = 10

Output

Explanation

The 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.

The Art of State Selection

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: Affects what decisions you can make going forward, OR Affects the value/cost of the optimal solution from this point And exclude everything else.

Common Pitfall: Over-Specifying State

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? In a grid pathfinding problem: my position changes In a knapsack problem: the remaining capacity changes In a string problem: the portion of string I've processed changes Question 2: What constraints must I respect? Can I use each item only once? \to Track which items are 'used' Is there a limit on consecutive actions? \to Track recent history Must subproblems remain independent? \to Track separability Question 3: What's the minimal set of variables that capture the above? Can I replace 'set of used items' with 'count of items considered'? Can I replace 'full history' with 'last K moves'? Can I encode multiple pieces of info into one variable?

State Analysis for Classic DP Problems
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

State Dimensionality: 1D, 2D, and Beyond

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): State: dp[i] where i is a single index or value Examples: Fibonacci, Climbing Stairs, Coin Change (by amount) State space: O(n) Classic pattern: Linear sequence problems where each position depends only on previous positions

1d_state_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# ===== 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): State: dp[i][j] where i and j are independent indices Examples: LCS, Edit Distance, Grid Paths, Knapsack State space: O(n \times m) Classic pattern: Two-sequence alignment, grid navigation, or 1D problem with additional constraint

2d_state_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# ===== 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): State: dp[i][j][k] or higher dimensions Examples: 3D shortest paths, string interleaving, multi-constraint problems State space: O(n \times m \times p) or higher Classic pattern: Problems with multiple independent constraints or multi-sequence alignment

3d_state_example.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# ===== 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 end

Dimensionality Rule of Thumb

Each independent constraint or sequence in your problem typically adds one dimension to your state. Two strings \to 2D. One sequence with a constraint \to 2D. Grid with limited resources \to 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.

State Space Analysis: Counting Your Subproblems

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 \times 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.

State Space Analysis for Common DP Problems
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) \times (m+1) \times (K+1) \approx O(n \times m \times 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.

state_space_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# ===== 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 jumps

State Space vs. Transition Count

Time complexity is O(states \times 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.

Common State Design Patterns

While every problem is unique, certain state design patterns appear repeatedly across DP problems. Recognizing these patterns accelerates your problem-solving dramatically.

The Major State Design Patterns

•Index-Based State: The most fundamental pattern. State = position in sequence(s). Examples: Fibonacci dp[i], LCS dp[i][j], Grid paths dp[r][c].
•Capacity/Resource State: Track remaining or used resources. Examples: Knapsack dp[i][w] (w = remaining capacity), Coin Change dp[amount] (remaining amount).
•Decision History State: Track recent decisions when they constrain future options. Examples: House Robber with cooldown dp[i][robbed_prev], Paint House dp[i][color].
•Interval State: Define subproblems by intervals [i, j]. Examples: Matrix Chain dp[i][j], Palindrome Partitioning dp[i][j], Burst Balloons dp[i][j].
•Bitmask State: When you need to track subset membership. Examples: TSP dp[mask][last], Assign Tasks dp[mask], Set Partition problems.
•Multi-Sequence State: Track positions in multiple sequences independently. Examples: Interleaving Strings 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.

Worked Example: Complete State Design Process

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 The current day (progresses from 0 to n-1) How many transactions we've completed (or are in) Whether we currently hold a stock or not 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

stock_iv_state_design.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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 implementation
def 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]

State Design Verification

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.

Summary: Mastering DP State Definition

We've covered the foundational skill of DP state design. Let's consolidate the key insights:

Key Takeaways

•DP state is a complete snapshot — It contains all and only the information needed to compute the optimal solution for a subproblem. It exhibits the Markov property: the future depends only on the state, not how you reached it.
•State selection is the critical skill — Include information that affects future decisions or values. Exclude everything else. Too little causes incorrect answers; too much causes intractable state spaces.
•Dimensionality equals independent pieces of information — Each independent constraint or sequence typically adds one dimension. 1D → O(n), 2D → O(n×m), 3D → O(n×m×k).
•State space analysis predicts complexity — Count distinct states and work per state. Time = O(states × work_per_state). Space = O(states), often reducible.
•Pattern recognition accelerates design — Index-based, capacity-based, decision-history, interval, bitmask—recognize which pattern fits and adapt it.
•Always verify your state — Every configuration maps to one state, space is tractable, transitions are definable, base cases are clear.

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.

Page Complete

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.

Data Structures & AlgorithmsState Design & Transition Functions

State Design & Transition Functions

LevelAdvanced

Duration90 mins

TopicState Design & Transition Functions

1 / 4

Defining DP State Precisely

The Heart of Dynamic Programming

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.

What You Will Learn

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.

What Is DP State?

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.

The Markov Property

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.

Fibonacci: The Simplest State

Consider computing the n-th Fibonacci number.

Input

n = 10

Output

Explanation

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.

The Art of State Selection

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: Affects what decisions you can make going forward, OR Affects the value/cost of the optimal solution from this point And exclude everything else.

Common Pitfall: Over-Specifying State

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? In a grid pathfinding problem: my position changes In a knapsack problem: the remaining capacity changes In a string problem: the portion of string I've processed changes Question 2: What constraints must I respect? Can I use each item only once? \to Track which items are 'used' Is there a limit on consecutive actions? \to Track recent history Must subproblems remain independent? \to Track separability Question 3: What's the minimal set of variables that capture the above? Can I replace 'set of used items' with 'count of items considered'? Can I replace 'full history' with 'last K moves'? Can I encode multiple pieces of info into one variable?

State Analysis for Classic DP Problems
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

State Dimensionality: 1D, 2D, and Beyond

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): State: dp[i] where i is a single index or value Examples: Fibonacci, Climbing Stairs, Coin Change (by amount) State space: O(n) Classic pattern: Linear sequence problems where each position depends only on previous positions

1d_state_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# ===== 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): State: dp[i][j] where i and j are independent indices Examples: LCS, Edit Distance, Grid Paths, Knapsack State space: O(n \times m) Classic pattern: Two-sequence alignment, grid navigation, or 1D problem with additional constraint

2d_state_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# ===== 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): State: dp[i][j][k] or higher dimensions Examples: 3D shortest paths, string interleaving, multi-constraint problems State space: O(n \times m \times p) or higher Classic pattern: Problems with multiple independent constraints or multi-sequence alignment

3d_state_example.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# ===== 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 end

Dimensionality Rule of Thumb

Each independent constraint or sequence in your problem typically adds one dimension to your state. Two strings \to 2D. One sequence with a constraint \to 2D. Grid with limited resources \to 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.

State Space Analysis: Counting Your Subproblems

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 \times 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.

State Space Analysis for Common DP Problems
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) \times (m+1) \times (K+1) \approx O(n \times m \times 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.

state_space_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# ===== 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 jumps

State Space vs. Transition Count

Time complexity is O(states \times 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.

Common State Design Patterns

While every problem is unique, certain state design patterns appear repeatedly across DP problems. Recognizing these patterns accelerates your problem-solving dramatically.

The Major State Design Patterns

•Index-Based State: The most fundamental pattern. State = position in sequence(s). Examples: Fibonacci dp[i], LCS dp[i][j], Grid paths dp[r][c].
•Capacity/Resource State: Track remaining or used resources. Examples: Knapsack dp[i][w] (w = remaining capacity), Coin Change dp[amount] (remaining amount).
•Decision History State: Track recent decisions when they constrain future options. Examples: House Robber with cooldown dp[i][robbed_prev], Paint House dp[i][color].
•Interval State: Define subproblems by intervals [i, j]. Examples: Matrix Chain dp[i][j], Palindrome Partitioning dp[i][j], Burst Balloons dp[i][j].
•Bitmask State: When you need to track subset membership. Examples: TSP dp[mask][last], Assign Tasks dp[mask], Set Partition problems.
•Multi-Sequence State: Track positions in multiple sequences independently. Examples: Interleaving Strings 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.

Worked Example: Complete State Design Process

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 The current day (progresses from 0 to n-1) How many transactions we've completed (or are in) Whether we currently hold a stock or not 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

stock_iv_state_design.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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 implementation
def 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]

State Design Verification

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.

Summary: Mastering DP State Definition

We've covered the foundational skill of DP state design. Let's consolidate the key insights:

Key Takeaways

•DP state is a complete snapshot — It contains all and only the information needed to compute the optimal solution for a subproblem. It exhibits the Markov property: the future depends only on the state, not how you reached it.
•State selection is the critical skill — Include information that affects future decisions or values. Exclude everything else. Too little causes incorrect answers; too much causes intractable state spaces.
•Dimensionality equals independent pieces of information — Each independent constraint or sequence typically adds one dimension. 1D → O(n), 2D → O(n×m), 3D → O(n×m×k).
•State space analysis predicts complexity — Count distinct states and work per state. Time = O(states × work_per_state). Space = O(states), often reducible.
•Pattern recognition accelerates design — Index-based, capacity-based, decision-history, interval, bitmask—recognize which pattern fits and adapt it.
•Always verify your state — Every configuration maps to one state, space is tractable, transitions are definable, base cases are clear.

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.

Page Complete

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.

Defining DP State Precisely

The Heart of Dynamic Programming

What Is DP State?

The Art of State Selection

State Dimensionality: 1D, 2D, and Beyond

State Space Analysis: Counting Your Subproblems

Common State Design Patterns

Worked Example: Complete State Design Process

Summary: Mastering DP State Definition

There’s more to understand.

Defining DP State Precisely

The Heart of Dynamic Programming

What Is DP State?

The Art of State Selection

State Dimensionality: 1D, 2D, and Beyond

State Space Analysis: Counting Your Subproblems

Common State Design Patterns

Worked Example: Complete State Design Process

Summary: Mastering DP State Definition

There’s more to understand.