# 1. Longest Common Sequence
def lcs(X, Y):
    m = len(X)
    n = len(Y)
    # Build the dp table bottom-up
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                
    # Backtrack to find the matching string
    lcs_str = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs_str.append(X[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
            
    # Reverse since we found characters from back to front
    lcs_str.reverse()
    
    return dp[m][n], "".join(lcs_str)

string1 = "ALONGWAY"
string2 = "longest"
string1=string1.lower()
string2=string2.lower()
length, sequence = lcs(string1, string2)

print(f"Length of LCS: {length}")
print(f"Matching String: {sequence}")


# 2. Matrix Chain Multiplication
def matrix_chain_order(p):
    n = len(p) - 1  # Number of matrices
    
    # dp[i][j] stores the minimum multiplications to compute matrix A_i...A_j
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    # L is the chain length (2 matrices, 3 matrices, etc.)
    for L in range(2, n + 1):
        for i in range(1, n - L + 2):
            j = i + L - 1
            dp[i][j] = float('inf') # Set to infinity to find the minimum
            
            # Try placing the parenthesis at every possible split point 'k'
            for k in range(i, j):
                # cost = cost of left subchain + cost of right subchain + cost of multiplying them
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    
    return dp[1][n]

# Dimensions of 3 matrices: A (10x20), B (20x30), C (30x40)
matrix_dims = [10, 20, 30, 40]
print(f"Minimum multiplications needed: {matrix_chain_order(matrix_dims)}")


# 3. Rod Cutting Problem
def rod_cutting(prices, n):
    dp = [0] * (n + 1)
    choices = [0] * (n + 1)
    
    for i in range(1, n + 1):
        max_val = -1
        for j in range(i):
            revenue = prices[j] + dp[i - j - 1]
            if revenue > max_val:
                max_val, choices[i] = revenue, j + 1
        dp[i] = max_val
        
    pieces = []
    while n > 0:
        pieces.append(choices[n])
        n -= choices[n]
        
    return dp[-1], pieces

# Example Usage:
rod_prices = [1, 5, 8, 9, 10, 17, 17, 20]
rod_length = 8
max_rev, chosen_pieces = rod_cutting(rod_prices, rod_length)

print(f"Max Revenue for length {rod_length}: {max_rev}")
print(f"Chosen pieces: {chosen_pieces}")
