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
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
102
103
104
105
106

# ===== EXAMPLE: 0/1 Knapsack Using Choice-Based Method =====
 
def derive_knapsack_transition():
    """
    Problem: Given n items with weights and values, maximize value 
             within capacity W.
    
    State: dp[i][w] = max value using items 0..i-1 with capacity w
    
    STEP 1: Identify Choices at state (i, w)
        Choice A: Don't take item i-1
        Choice B: Take item i-1 (only if weight[i-1] <= w)
    
    STEP 2: Map Choices to Sub-States
        Choice A → dp[i-1][w] 
                   (same capacity, one less item considered)
        Choice B → dp[i-1][w - weight[i-1]]
                   (reduced capacity, one less item considered)
    
    STEP 3: Express Values
        Value of A = dp[i-1][w] + 0 (no value gained)
        Value of B = dp[i-1][w - weight[i-1]] + value[i-1]
    
    STEP 4: Aggregate (maximization)
        dp[i][w] = max(
            dp[i-1][w],                               # Choice A
            dp[i-1][w - weight[i-1]] + value[i-1]     # Choice B
        )
        
        (with condition: Choice B only valid if weight[i-1] <= w)
    """
    pass
 
 
# ===== EXAMPLE: Edit Distance Using Choice-Based Method =====
 
def derive_edit_distance_transition():
    """
    Problem: Minimum operations (insert, delete, replace) to transform 
             word1 into word2.
    
    State: dp[i][j] = min edits to transform word1[0..i-1] to word2[0..j-1]
    
    STEP 1: Identify Choices at state (i, j)
        If word1[i-1] == word2[j-1]:
            Choice A: Match characters (no operation needed)
        
        If word1[i-1] != word2[j-1]:
            Choice B: Replace word1[i-1] with word2[j-1]
            Choice C: Delete word1[i-1]
            Choice D: Insert word2[j-1] into word1
    
    STEP 2: Map Choices to Sub-States
        Choice A → dp[i-1][j-1] (both advance)
        Choice B → dp[i-1][j-1] (both advance after replace)
        Choice C → dp[i-1][j]   (word1 advances, word2 stays)
        Choice D → dp[i][j-1]   (word1 stays, word2 advances)
    
    STEP 3: Express Values
        Value of A = dp[i-1][j-1] + 0 (no edit)
        Value of B = dp[i-1][j-1] + 1 (one edit)
        Value of C = dp[i-1][j] + 1   (one edit)
        Value of D = dp[i][j-1] + 1   (one edit)
    
    STEP 4: Aggregate (minimization)
        if word1[i-1] == word2[j-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = 1 + min(
                dp[i-1][j-1],  # Replace
                dp[i-1][j],    # Delete
                dp[i][j-1]     # Insert
            )
    """
    pass
 
 
# ===== EXAMPLE: Unique Paths (Counting) Using Choice-Based Method =====
 
def derive_unique_paths_transition():
    """
    Problem: Count paths from (0,0) to (m-1, n-1) moving only right/down.
    
    State: dp[r][c] = number of paths to reach cell (r, c)
    
    STEP 1: Identify Choices (how could we ARRIVE at (r, c)?)
        Choice A: Come from above (r-1, c)
        Choice B: Come from left (r, c-1)
    
    NOTE: For counting, we think "how did we get here?" not 
          "where can we go?"
    
    STEP 2: Map Choices to Sub-States
        Choice A → dp[r-1][c]
        Choice B → dp[r][c-1]
    
    STEP 3: Express Values
        Value of A = dp[r-1][c] × 1 (all paths to (r-1,c) extend here)
        Value of B = dp[r][c-1] × 1 (all paths to (r,c-1) extend here)
    
    STEP 4: Aggregate (counting = sum)
        dp[r][c] = dp[r-1][c] + dp[r][c-1]
        
        (with boundary conditions for first row/column)
    """
    pass

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

# ===== BACKWARD (PULL) TRANSITION: Coin Change =====
def coin_change_backward(coins: list[int], amount: int) -> int:
    """
    Backward formulation: for each amount, PULL from smaller amounts.
    
    dp[a] = min over all coins c of { dp[a - c] + 1 }
    
    "To make amount a, look at each coin c and check what it would cost
     to have already made (a - c), then add one coin."
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 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)  # PULL from dp[a - coin]
    
    return dp[amount] if dp[amount] != float('inf') else -1
 
 
# ===== FORWARD (PUSH) TRANSITION: Coin Change =====
def coin_change_forward(coins: list[int], amount: int) -> int:
    """
    Forward formulation: for each amount, PUSH to larger amounts.
    
    for each coin c:
        dp[a + c] = min(dp[a + c], dp[a] + 1)
    
    "Having made amount a with cost dp[a], I can make amount (a + c)
     by adding one coin of value c."
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for a in range(amount):
        if dp[a] == float('inf'):
            continue
        for coin in coins:
            if a + coin <= amount:
                dp[a + coin] = min(dp[a + coin], dp[a] + 1)  # PUSH to dp[a + coin]
    
    return dp[amount] if dp[amount] != float('inf') else -1
 
 
# ===== FORWARD MORE NATURAL: Jump Game II =====
def jump_game_forward(nums: list[int]) -> int:
    """
    Forward is more natural here: from each position, we know
    where we CAN jump to, not necessarily where we came from.
    
    From position i, we can reach positions i+1, i+2, ..., i+nums[i]
    """
    n = len(nums)
    if n <= 1:
        return 0
    
    dp = [float('inf')] * n
    dp[0] = 0
    
    for i in range(n):
        if dp[i] == float('inf'):
            continue
        # PUSH: from i, update all reachable positions
        for j in range(i + 1, min(i + nums[i] + 1, n)):
            dp[j] = min(dp[j], dp[i] + 1)
    
    return dp[n - 1] if dp[n - 1] != float('inf') else -1
 
 
# ===== BACKWARD MORE NATURAL: Stone Game =====
def stone_game_backward(piles: list[int]) -> bool:
    """
    Backward is natural for interval DP: we pull from smaller intervals.
    
    dp[i][j] = max stones player can get from piles[i..j]
    
    "To know the best score for interval [i, j], look at what happens
     after taking from either end."
    """
    n = len(piles)
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single pile
    for i in range(n):
        dp[i][i] = piles[i]
    
    # Expand intervals
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # PULL from smaller intervals [i+1, j] and [i, j-1]
            take_left = piles[i] + (sum(piles[i+1:j+1]) - dp[i+1][j])
            take_right = piles[j] + (sum(piles[i:j]) - dp[i][j-1])
            dp[i][j] = max(take_left, take_right)
    
    total = sum(piles)
    return dp[0][n-1] > total - dp[0][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
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

# ===== PATTERN: Linear Recurrence =====
def fibonacci_pattern(n: int) -> int:
    """
    Pattern: dp[i] = dp[i-1] + dp[i-2]
    
    Fixed look-back depth (2), linear state space.
    Many problems reduce to this pattern with different coefficients.
    """
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
 
 
# ===== PATTERN: Take/Skip =====
def house_robber_pattern(nums: list[int]) -> int:
    """
    Pattern: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    Binary choice at each position:
        - Skip: carry forward previous best
        - Take: use value, skip to i-2 (due to constraint)
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[-1]
 
 
# ===== PATTERN: Interval DP =====
def longest_palindrome_subsequence(s: str) -> int:
    """
    Pattern: dp[i][j] = f(dp[i+1][j-1], dp[i][j-1], dp[i+1][j])
    
    Build larger intervals from smaller ones.
    Process in order of increasing interval length.
    """
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single characters
    for i in range(n):
        dp[i][i] = 1
    
    # Expand intervals
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    
    return dp[0][n-1]
 
 
# ===== PATTERN: State Machine =====
def stock_with_cooldown_pattern(prices: list[int]) -> int:
    """
    Pattern: Multiple states with different transitions
    
    States: hold, sold (in cooldown), rest (can buy)
    Transitions form a state machine:
        rest → hold (buy)
        hold → sold (sell)
        sold → rest (cooldown ends)
    """
    if not prices:
        return 0
    
    n = len(prices)
    hold = [0] * n   # Holding stock
    sold = [0] * n   # Just sold, in cooldown
    rest = [0] * n   # Not holding, can buy
    
    hold[0] = -prices[0]
    sold[0] = 0
    rest[0] = 0
    
    for i in range(1, n):
        # Each state has its own transition equation:
        hold[i] = max(hold[i-1], rest[i-1] - prices[i])
        sold[i] = hold[i-1] + prices[i]
        rest[i] = max(rest[i-1], sold[i-1])
    
    return max(sold[-1], rest[-1])
 
 
# ===== PATTERN: Sequence Alignment =====
def lcs_pattern(text1: str, text2: str) -> int:
    """
    Pattern: dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], dp[i][j-1]
    
    The diagonal, left, and up dependencies are characteristic of
    two-sequence alignment problems.
    """
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  # Diagonal + match
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # Left or up
    
    return dp[m][n]

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

# ===== COMPLETE DERIVATION: Word Break Problem =====
 
def word_break_derivation(s: str, wordDict: list[str]) -> bool:
    """
    STEP 1: Semantic Meaning
        dp[i] = True if s[0..i-1] can be segmented into dictionary words
        dp[i] = False otherwise
        
        What does dp[i] represent? "Can the first i characters be segmented?"
    
    STEP 2: Last Decisions
        If dp[i] is True, what was the last word used?
        The last word must end at position i-1.
        So the last word is s[j:i] for some j where 0 <= j < i.
        
        For dp[i] to be True:
            - dp[j] must be True (prefix s[0..j-1] is segmentable)
            - s[j:i] must be in wordDict (the "bridge" is a valid word)
    
    STEP 3: Case Contribution
        dp[i] = True if there exists j such that:
            dp[j] = True AND s[j:i] in wordDict
        
        dp[i] = False otherwise (no valid segmentation)
    
    STEP 4: Aggregate
        Feasibility problem → use logical OR
        dp[i] = any(dp[j] and s[j:i] in wordDict for j in range(i))
    """
    n = len(s)
    word_set = set(wordDict)
    
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string is trivially valid
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # Early termination for feasibility
    
    return dp[n]
 
 
# ===== COMPLETE DERIVATION: Decode Ways =====
 
def decode_ways_derivation(s: str) -> int:
    """
    STEP 1: Semantic Meaning
        dp[i] = number of ways to decode s[0..i-1]
        
        "How many valid letter sequences decode the first i digits?"
    
    STEP 2: Last Decisions
        At position i-1 (0-indexed), we decoded either:
        (a) One digit (s[i-1]) as a letter (1-9 → A-I)  
        (b) Two digits (s[i-2:i]) as a letter (10-26 → J-Z)
    
    STEP 3: Case Contribution
        (a) If s[i-1] in '123456789':
            Ways = dp[i-1] (all ways to decode s[0..i-2], extend each by one letter)
        (b) If s[i-2:i] forms valid 2-digit:
            Ways = dp[i-2] (all ways to decode s[0..i-3], extend each by one letter)
    
    STEP 4: Aggregate
        Counting problem → use SUM
        dp[i] = (contribution from case a) + (contribution from case b)
    """
    if not s or s[0] == '0':
        return 0
    
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # Base: empty string has one "decoding" (nothing)
    dp[1] = 1  # First character (already validated non-zero)
    
    for i in range(2, n + 1):
        # Case (a): single digit s[i-1]
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        
        # Case (b): two digits s[i-2:i]
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i-2]
    
    return dp[n]
 
 
# ===== COMPLETE DERIVATION: Minimum Path Sum =====
 
def min_path_sum_derivation(grid: list[list[int]]) -> int:
    """
    STEP 1: Semantic Meaning
        dp[r][c] = minimum path sum to reach cell (r, c) from (0, 0)
        
        "What's the smallest sum path to get here?"
    
    STEP 2: Last Decisions
        To reach (r, c), we came from:
        (a) Cell above: (r-1, c)
        (b) Cell to left: (r, c-1)
    
    STEP 3: Case Contribution
        (a) From above: dp[r-1][c] + grid[r][c]
        (b) From left:  dp[r][c-1] + grid[r][c]
    
    STEP 4: Aggregate
        Minimization → use MIN
        dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + grid[r][c]
        
        Boundary: First row can only come from left
                  First column can only come from above
    """
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    dp[0][0] = grid[0][0]
    
    # First row: only from left
    for c in range(1, n):
        dp[0][c] = dp[0][c-1] + grid[0][c]
    
    # First column: only from above
    for r in range(1, m):
        dp[r][0] = dp[r-1][0] + grid[r][0]
    
    # Interior: min of both
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + grid[r][c]
    
    return dp[m-1][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
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

# ===== VERIFICATION EXAMPLE: Matrix Chain Multiplication =====
 
def verify_matrix_chain():
    """
    State: dp[i][j] = min cost to multiply matrices i through j
    
    CHECK 1: Acyclicity
        dp[i][j] depends on dp[i][k] and dp[k+1][j] where i <= k < j
        Since (k-i) < (j-i) and (j-k-1) < (j-i), we always access
        smaller intervals. ✓ Acyclic
    
    CHECK 2: Completeness
        For interval [i, j], we can split at any k from i to j-1.
        We try all k values: no splits are missed. ✓ Complete
    
    CHECK 3: Correct Aggregate
        We want minimum cost → use min. ✓ Correct
        
    CHECK 4: Base Cases
        dp[i][i] = 0 (single matrix, no multiplication needed)
        All intervals of length 1 are covered. ✓ Base cases defined
    """
    pass
 
 
def matrix_chain_order(dims: list[int]) -> int:
    """
    dims[i-1] × dims[i] gives dimensions of matrix i.
    Find minimum multiplications to compute product of all matrices.
    
    Transition: dp[i][j] = min over k of { dp[i][k] + dp[k+1][j] + cost(split at k) }
    """
    n = len(dims) - 1  # Number of matrices
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single matrix (length 1 intervals)
    for i in range(n):
        dp[i][i] = 0
    
    # Fill by increasing interval length
    for length in range(2, n + 1):  # length of interval
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                # Cost = left side + right side + cost of multiplying results
                cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]
 
 
# ===== HAND-TRACING: The Ultimate Verification =====
def hand_trace_coin_change():
    """
    For simple inputs, trace the DP table by hand.
    
    coins = [1, 2, 5], amount = 6
    
    Initial: dp = [0, inf, inf, inf, inf, inf, inf]
    
    a=1: coin 1: dp[1] = min(inf, dp[0]+1) = 1
    a=2: coin 1: dp[2] = min(inf, dp[1]+1) = 2
         coin 2: dp[2] = min(2, dp[0]+1) = 1
    a=3: coin 1: dp[3] = min(inf, dp[2]+1) = 2
         coin 2: dp[3] = min(2, dp[1]+1) = 2
    a=4: coin 1: dp[4] = min(inf, dp[3]+1) = 3
         coin 2: dp[4] = min(3, dp[2]+1) = 2
    a=5: coin 1: dp[5] = min(inf, dp[4]+1) = 3
         coin 2: dp[5] = min(3, dp[3]+1) = 3
         coin 5: dp[5] = min(3, dp[0]+1) = 1
    a=6: coin 1: dp[6] = min(inf, dp[5]+1) = 2
         coin 2: dp[6] = min(2, dp[4]+1) = 2
         coin 5: dp[6] = min(2, dp[1]+1) = 2
    
    Final: dp = [0, 1, 1, 2, 2, 1, 2]
    Answer: dp[6] = 2 (either 5+1 or 2+2+2)
    
    Hand tracing confirms the transition is correct!
    """
    coins = [1, 2, 5]
    amount = 6
    dp = [float('inf')] * (amount + 1)
    dp[0] = 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]  # Returns 2