# 1. Longest Common Sequence
# For string lengths m and n: O(mn) time and O(mn) space.
def lcs(first, second):
    rows, cols = len(first), len(second)
    dp = [[0] * (cols + 1) for _ in range(rows + 1)]

    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            if first[i - 1] == second[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    sequence = []
    i, j = rows, cols
    while i and j:
        if first[i - 1] == second[j - 1]:
            sequence.append(first[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    sequence.reverse()
    return dp[rows][cols], "".join(sequence)


first, second = "ALONGWAY".lower(), "longest".lower()
length, sequence = lcs(first, second)
print(f"Length of LCS: {length}")
print(f"Matching String: {sequence}")


# 2. Matrix Chain Multiplication
# For n matrices: O(n^3) time and O(n^2) space.
def matrix_chain_order(dimensions):
    n = len(dimensions) - 1
    if n <= 0:
        return 0

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for size in range(2, n + 1):
        for i in range(1, n - size + 2):
            j = i + size - 1
            dp[i][j] = float("inf")
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + dimensions[i - 1] * dimensions[k] * dimensions[j]
                dp[i][j] = min(dp[i][j], cost)

    return dp[1][n]


dimensions = [10, 20, 30, 40]
print(f"Minimum multiplications needed: {matrix_chain_order(dimensions)}")


# 3. Rod Cutting Problem
# For rod length n: O(n^2) time and O(n) space.
def rod_cutting(prices, length):
    if length < 0 or length > len(prices):
        raise ValueError("Length must be between 0 and the number of prices.")

    dp = [0] * (length + 1)
    choices = [0] * (length + 1)

    for size in range(1, length + 1):
        best = float("-inf")
        for cut in range(size):
            revenue = prices[cut] + dp[size - cut - 1]
            if revenue > best:
                best, choices[size] = revenue, cut + 1
        dp[size] = best

    pieces = []
    while length:
        pieces.append(choices[length])
        length -= choices[length]

    return dp[-1], pieces


prices = [1, 5, 8, 9, 10, 17, 17, 20]
length = 8
revenue, pieces = rod_cutting(prices, length)
print(f"Max Revenue for length {length}: {revenue}")
print(f"Chosen pieces: {pieces}")
