Common DP Patterns

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

def matrix_chain_order(p: list[int]) -> int:
    """
    Find minimum number of scalar multiplications to multiply
    a chain of matrices with dimensions given by p.
    
    Matrix i has dimensions p[i-1] x p[i].
    So for n matrices, p has n+1 elements.
    
    Returns: Minimum number of scalar multiplications.
    
    Time Complexity: O(n³)
    Space Complexity: O(n²)
    """
    n = len(p) - 1  # Number of matrices
    
    if n == 0:
        return 0
    
    # dp[i][j] = min cost to multiply matrices i through j (1-indexed)
    # We'll use 1-indexed for matrices, so dp size is (n+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    # Base case: single matrix costs 0
    # dp[i][i] = 0 (already initialized)
    
    # Fill by increasing chain length
    for length in range(2, n + 1):  # length of chain
        for i in range(1, n - length + 2):  # start of chain
            j = i + length - 1  # end of chain
            dp[i][j] = float('inf')
            
            # Try all split points
            for k in range(i, j):
                # Cost = cost of left part + cost of right part + cost of final multiplication
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[1][n]
 
 
def matrix_chain_with_solution(p: list[int]) -> tuple[int, str]:
    """
    Extended version that also returns the optimal parenthesization.
    """
    n = len(p) - 1
    
    if n == 0:
        return 0, ""
    if n == 1:
        return 0, "A1"
    
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    split = [[0] * (n + 1) for _ in range(n + 1)]  # Records where to split
    
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    split[i][j] = k  # Remember the optimal split point
    
    def build_solution(i: int, j: int) -> str:
        if i == j:
            return f"A{i}"
        k = split[i][j]
        left = build_solution(i, k)
        right = build_solution(k + 1, j)
        return f"({left} × {right})"
    
    return dp[1][n], build_solution(1, n)
 
 
# Example usage
if __name__ == "__main__":
    # Dimensions: A1 is 10x100, A2 is 100x5, A3 is 5x50
    dimensions = [10, 100, 5, 50]
    
    min_cost = matrix_chain_order(dimensions)
    print(f"Minimum multiplications: {min_cost}")
    
    min_cost, parenthesization = matrix_chain_with_solution(dimensions)
    print(f"Optimal parenthesization: {parenthesization}")
    print(f"Total cost: {min_cost}")
    
    # Output:
    # Minimum multiplications: 7500
    # Optimal parenthesization: ((A1 × A2) × A3)
    # Total cost: 7500

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

def max_coins(nums: list[int]) -> int:
    """
    Find maximum coins by bursting all balloons optimally.
    
    Key insight: Think backwards - which balloon is burst LAST in each interval?
    
    Time Complexity: O(n³)
    Space Complexity: O(n²)
    """
    # Add virtual balloons at boundaries
    balloons = [1] + nums + [1]
    n = len(balloons)
    
    # dp[i][j] = max coins from bursting all balloons in open interval (i, j)
    # Balloons i and j are boundaries, not to be burst in this subproblem
    dp = [[0] * n for _ in range(n)]
    
    # Process by interval length
    for length in range(2, n):  # length from 2 to n-1
        for i in range(n - length):
            j = i + length
            
            # Try each balloon k in (i, j) as the LAST one to burst
            for k in range(i + 1, j):
                # Coins from left, right, and bursting k last
                coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]
                dp[i][j] = max(dp[i][j], coins)
    
    # Answer is for interval (0, n-1), which is the entire original array
    return dp[0][n - 1]
 
 
def max_coins_with_order(nums: list[int]) -> tuple[int, list[int]]:
    """
    Extended version that also returns the optimal burst order.
    """
    balloons = [1] + nums + [1]
    n = len(balloons)
    
    dp = [[0] * n for _ in range(n)]
    last = [[0] * n for _ in range(n)]  # Which balloon is burst last in (i, j)
    
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            
            for k in range(i + 1, j):
                coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
                    last[i][j] = k
    
    def reconstruct(i: int, j: int) -> list[int]:
        """Reconstruct burst order from the 'last' table."""
        if j <= i + 1:
            return []
        
        k = last[i][j]
        # First burst everything except k
        left_order = reconstruct(i, k)
        right_order = reconstruct(k, j)
        # Then burst k (converted back to 0-indexed original)
        return left_order + right_order + [k - 1]  # k-1 because we added boundary
    
    order = reconstruct(0, n - 1)
    return dp[0][n - 1], order
 
 
# Example
if __name__ == "__main__":
    nums = [3, 1, 5, 8]
    
    max_coins_value = max_coins(nums)
    print(f"Maximum coins: {max_coins_value}")
    
    max_coins_value, burst_order = max_coins_with_order(nums)
    print(f"Maximum coins: {max_coins_value}")
    print(f"Burst order (0-indexed): {burst_order}")
    
    # Verify: simulate the burst order
    remaining = list(nums)
    total = 0
    for idx in burst_order:
        # Find actual position after previous bursts
        left = remaining[idx - 1] if idx > 0 else 1
        right = remaining[idx + 1] if idx < len(remaining) - 1 else 1
        coins = left * remaining[idx] * right
        total += coins
        print(f"  Burst balloon {remaining[idx]} at position {idx}: {left}×{remaining[idx]}×{right} = {coins}")
        remaining.pop(idx)
    
    print(f"Total verified: {total}")

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

def optimal_bst(keys: list, prob: list[float]) -> tuple[float, list[list[int]]]:
    """
    Find the optimal BST minimizing expected search cost.
    
    Args:
        keys: Sorted list of keys
        prob: prob[i] = access probability of keys[i]
    
    Returns:
        Tuple of (minimum expected cost, root table for reconstruction)
    
    Time Complexity: O(n³) - can be optimized to O(n²) using Knuth's optimization
    Space Complexity: O(n²)
    """
    n = len(keys)
    
    if n == 0:
        return 0.0, []
    
    # Precompute prefix sums for O(1) range sum queries
    prefix_sum = [0.0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + prob[i]
    
    def weight(i: int, j: int) -> float:
        """Sum of probabilities from index i to j (0-indexed, inclusive)."""
        if i > j:
            return 0.0
        return prefix_sum[j + 1] - prefix_sum[i]
    
    # dp[i][j] = min expected cost for keys[i..j]
    # Using n+2 size to handle boundary cases elegantly
    dp = [[0.0] * (n + 1) for _ in range(n + 2)]
    root = [[0] * (n + 1) for _ in range(n + 2)]
    
    # Base case: single keys
    for i in range(n):
        dp[i][i] = prob[i]
        root[i][i] = i
    
    # Fill by increasing length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            w = weight(i, j)
            
            # Try each key as root
            for r in range(i, j + 1):
                # Cost of left subtree (if exists)
                left_cost = dp[i][r - 1] if r > i else 0.0
                # Cost of right subtree (if exists)
                right_cost = dp[r + 1][j] if r < j else 0.0
                
                cost = w + left_cost + right_cost
                
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    root[i][j] = r
    
    return dp[0][n - 1], root
 
 
def print_optimal_bst(keys: list, root: list[list[int]], i: int, j: int, 
                      parent: str = "", direction: str = "Root"):
    """Recursively print the structure of the optimal BST."""
    if i > j:
        return
    
    r = root[i][j]
    if parent:
        print(f"  {keys[r]} is {direction} child of {parent}")
    else:
        print(f"  {keys[r]} is the Root")
    
    print_optimal_bst(keys, root, i, r - 1, keys[r], "left")
    print_optimal_bst(keys, root, r + 1, j, keys[r], "right")
 
 
# Example
if __name__ == "__main__":
    # Keys and their access frequencies
    keys = ['A', 'B', 'C', 'D', 'E']
    probabilities = [0.25, 0.20, 0.05, 0.20, 0.30]  # Must sum to 1
    
    min_cost, root_table = optimal_bst(keys, probabilities)
    
    print(f"Keys: {keys}")
    print(f"Probabilities: {probabilities}")
    print(f"Minimum expected search cost: {min_cost:.4f}")
    print(f"
Optimal BST structure:")
    print_optimal_bst(keys, root_table, 0, len(keys) - 1)
    
    # The optimal BST might look quite different from a balanced tree
    # because frequently accessed keys should be near the root