2.动态规划法求解最长公共子序列问题的算法伪代码描述

算法描述：

设有两个序列A和B，长度分别为m和n，求它们的最长公共子序列。

动态规划法的基本思路是：用一个二维数组dp[m+1][n+1]表示A和B的任意子序列的LCS长度，其中dp[i][j]表示A[1..i]和B[1..j]的LCS长度。则可以得到状态转移方程：

当 A[i] == B[j] 时：dp[i][j] = dp[i-1][j-1] + 1;

当 A[i] != B[j] 时：dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

最终的LCS长度即为dp[m][n]。

伪代码描述：

func longestCommonSubsequence(A[1..m], B[1..n])
// 初始化二维数组
dp[0..m][0..n] = 0

for i = 1 to m
for j = 1 to n
if A[i] == B[j]
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]

相关问题

动态规划法求解最长公共子序列问题的算法伪代码描述

下面是求解最长公共子序列问题的动态规划算法伪代码：

function lcs_length(X, Y)
    m = length(X)
    n = length(Y)
    let c[0..m, 0..n] be a table
    for i = 0 to m
        c[i, 0] = 0
    for j = 0 to n
        c[0, j] = 0
    for i = 1 to m
        for j = 1 to n
            if X[i] == Y[j]
                c[i, j] = c[i-1, j-1] + 1
            else
                c[i, j] = max(c[i-1, j], c[i, j-1])
    return c[m, n]

其中，X和Y是要比较的两个字符串，m和n分别是它们的长度。c[i, j]表示X的前i个字符和Y的前j个字符的最长公共子序列的长度。该算法的时间复杂度为O(mn)。

动态规划法求解数塔问题的算法伪代码描述

以下是数塔问题的动态规划算法伪代码描述：

1. 读入数塔高度 n 和数塔数组 a[n][n]；

2. 从倒数第二层开始，自底向上逐层计算：

- 对于第 i 层的每一个 j，计算出 a[i][j] 加上下一层相邻的两个数中的最大值（即 a[i+1][j] 和 a[i+1][j+1]）；

- 将计算结果保存在 a[i][j] 中；

3. 最终，a[0][0] 即为数塔顶部到底部的最大路径和。

完整的Python代码如下：

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))

for i in range(n-2, -1, -1):
    for j in range(i+1):
        a[i][j] += max(a[i+1][j], a[i+1][j+1])

print(a[0][0])