State Design & Transition Functions

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]

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]

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

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

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]