常见字符串的算法说明

Question

问题定义：

给出两个长度相等的字符串a和b，那么最长的字符串（S）可以构造为S是a和b的子代。如果可以通过从y中删除0个或多个字符来形成x，则将字符串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]);
  }
}

任何人都遇到过这个问题，并使用这样的解决方案解决了吗？我以另一种方式解决了它。只是发现此解决方案很优雅，但到目前为止还没有任何意义。任何人都可以帮忙解释一下。

[问题定义：给定两个长度相等的字符串a和b，可以构造的最长字符串（S）是什么，使得S是a和b的子代。字符串x被认为是...的子级。

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]和[ C0]包含最多字符。