常见字符串的算法解释

Question

问题定义:

给定两个长度相等的字符串 a 和 b，可以构造的最长字符串 (S) 是多少，使得 S 是 a 和 b 的子字符串。 如果 x 可以通过从 y 中删除 0 个或多个字符来形成，则字符串 x 被称为字符串 y 的子代

输入格式

两个字符串 a 和 b，用换行符分隔它们

约束

所有字符均为大写且位于 ascii 值 65-90 之间。字符串的最大长度为 5000

输出格式

字符串S的长度

示例输入 #0

哈利 莎莉

示例输出 #0

2

从 HARRY 和 SALLY 中删除零个或多个字符后可能得到的最长字符子集是 AY，其长度为 2。

解决方案:

public class Solution {
  public static void main(String[] args) throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    char[] a = in.readLine().toCharArray();
    char[] b = in.readLine().toCharArray();
    int[][] dp = new int[a.length + 1][b.length + 1];
    dp[0][0] = 1;
    for (int i = 0; i < a.length; i++)
        for (int j = 0; j < b.length; j++)
           if (a[i] == b[j])
              dp[i + 1][j + 1] = dp[i][j] + 1;
           else
              dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
              System.out.println(dp[a.length][b.length]);
  }
}

有人遇到过这个问题并使用这样的解决方案解决了吗？我用不同的方式解决了它。只发现这个解决方案很优雅，但到目前为止还无法理解它。谁能帮忙解释一下。

Answer 1

该算法使用 Dynamic Programming 。理解动态编程的关键点是理解递归步骤，在本例中是在 if-else 语句中。我对大小矩阵 (a.length+1) * (b.length +1) 的理解是，对于矩阵中的给定元素 dp[i +1, j +1 ] 它表示如果我们只比较字符串 a[0:i] 和 b[0:j] ，这两个字符串的子代将是什么 >a[0:i] 和 b[0:j] 包含最多字符。

为了理解递归步骤，让我们看一下“HARRY”和“SALLY”的例子，假设我正在计算dp[5][5]的步骤，在这个在这种情况下，我将查看最后一个字符'Y':

A.如果 a[4] 和 b[4] 相等，在本例中 "Y"= "Y"，那么我知道最佳值解决方案是: 1) 找出 "HARR" 和 "SALL" 的子代中包含最多字符(假设为 n 个字符)，然后 2) 添加 1 到 n。

B.如果 a[4] 和 b[4] 不相等，则最佳解决方案是 "HARR" 和 的子级“SALLY” 或 “HARRY” 和 “SALL” 的子代，将转换为 Max(dp[i+1][j] 和dp[i][j+1]) 在代码中。