本关任务：编写用动态规划解决最长公共子序列问题。求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列

动态规划（Dynamic Programming）是一种常用的解决优化问题的方法，它通常用于求解最优化问题。最长公共子序列问题就是一个经典的动态规划问题。

最长公共子序列（Longest Common Subsequence，简称LCS）问题是指：给定两个字符串S1和S2，求它们的最长公共子序列。

最长公共子序列的长度是指在两个给定序列中同时出现的最长子序列的长度。例如，字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列是“BDAB”，长度为4。

下面是使用动态规划求解最长公共子序列问题的具体步骤：

1. 定义状态：设dp[i][j]表示S1的前i个字符和S2的前j个字符的最长公共子序列的长度。

2. 初始化状态：dp[0][j]=dp[i][0]=0。

3. 状态转移方程：如果S1的第i个字符等于S2的第j个字符，则dp[i][j]=dp[i-1][j-1]+1；否则，dp[i][j]=max(dp[i-1][j], dp[i][j-1])。

4. 返回结果：dp[m][n]即为S1和S2的最长公共子序列的长度，其中m和n分别为S1和S2的长度。

下面是使用动态规划求解最长公共子序列问题的Python代码实现：

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

s1 = 'ABCDBAB'
s2 = 'BDCABA'
print(longest_common_subsequence(s1, s2))  # 输出4，即最长公共子序列“BDAB”的长度

在上面的代码中，我们采用了二维数组dp来记录状态，其中dp[i][j]表示S1的前i个字符和S2的前j个字符的最长公共子序列的长度。在状态转移方程中，如果S1的第i个字符等于S2的第j个字符，则dp[i][j]=dp[i-1][j-1]+1；否则，dp[i][j]=max(dp[i-1][j], dp[i][j-1])。最终返回dp[m][n]即为S1和S2的最长公共子序列的长度，其中m和n分别为S1和S2的长度。