头歌算法实验六 动态规划2

1.矩阵连乘问题

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * n for _ in range(n)]
    s = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                if q < m[i][j]:
                    m[i][j], s[i][j] = q, k

    return s

def print_optimal_parens(s, i, j):
    return f"A{i + 1}" if i == j else "(" + print_optimal_parens(s, i, s[i][j]) + print_optimal_parens(s, s[i][j] + 1, j) + ")"

if __name__ == "__main__":
    dimensions = [3, 2, 5, 10, 2, 3]  
    s = matrix_chain_order(dimensions)
    result = print_optimal_parens(s, 0, len(dimensions) - 2)
    print('最优括号化方式:', result)

2.最长公共子序列问题

def LCS(X, Y):
    n, m = len(X), len(Y)
    c = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 构建长度矩阵
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    
    # 回溯找到LCS
    lcs = []
    while n > 0 and m > 0:
        if X[n - 1] == Y[m - 1]:
            lcs.append(X[n - 1])
            n -= 1
            m -= 1
        elif c[n - 1][m] >= c[n][m - 1]:
            n -= 1
        else:
            m -= 1

    return lcs[::-1]  # 反转以获得正确顺序

if __name__ == "__main__":
    A = ['z', 'x', 'y', 'x', 'y', 'z']
    B = ['x', 'y', 'y', 'z', 'x']
    print(LCS(A, B))  # 输出：['y', 'y', 'z']

3.最长公共子串问题

def longest_common_substring(X, Y):
    m, n = len(X), len(Y)
    longest_length, end_index = 0, 0
    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
                if dp[i][j] > longest_length:
                    longest_length, end_index = dp[i][j], i

    return X[end_index - longest_length:end_index]
X, Y = "ABABC", "BABCA"
print('最长公共子串:', longest_common_substring(X, Y))