最长公共子序列 matlab代码

最长公共子序列（Longest Common Subsequence，简称LCS）是指在两个序列中找到最长的公共子序列的问题。下面是一个用Matlab实现最长公共子序列的代码示例：

function lcs = longestCommonSubsequence(str1, str2)
    m = length(str1);
    n = length(str2);
    
    % 创建一个二维数组来保存最长公共子序列的长度
    dp = zeros(m+1, n+1);
    
    % 动态规划计算最长公共子序列的长度
    for i = 1:m
        for j = 1:n
            if str1(i) == str2(j)
                dp(i+1, j+1) = dp(i, j) + 1;
            else
                dp(i+1, j+1) = max(dp(i+1, j), dp(i, j+1));
            end
        end
    end
    
    % 根据dp数组回溯找到最长公共子序列
    lcs = '';
    i = m;
    j = n;
    while i > 0 && j > 0
        if str1(i) == str2(j)
            lcs = [str1(i), lcs];
            i = i - 1;
            j = j - 1;
        elseif dp(i+1, j) > dp(i, j+1)
            j = j - 1;
        else
            i = i - 1;
        end
    end
end

使用示例：

str1 = 'ABCDAB';
str2 = 'BDCAB';
lcs = longestCommonSubsequence(str1, str2);
disp(lcs);

输出结果为：

BDAB